Submission #6156509


Source Code Expand

from collections import Counter
from collections import deque
from functools import reduce
from pprint import pprint
import bisect
import copy
import fractions
import itertools
import math
import queue
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers): return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers): return reduce(LCM, numbers)
def LCM(m, n): return (m * n // fractions.gcd(m, n))
class UnionFind():

    def __init__(self, n):
        self.n = n
        self.node = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

    def same(self, x, y):
        return bool(self.root(x) == self.root(y))

    def root(self, x):
        if self.node[x] == x:
            return x
        else:
            self.node[x] = self.root(self.node[x])  # 経路圧縮
            return self.node[x]

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x == y:
            return  # 結合不要
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.node[y] = x
        self.size[x] += self.size[y]

    def return_size(self, x):
        return self.size[self.root(x)]


n = II()
if n == 1 or n == 2:
    print(n)
else:
    # まにあわない
    dp = [[] for _ in range(n+1)]
    dp[1].append(1)
    dp[2].append(2)
    max_element = [[] for _ in range(n+1)]
    max_element[0] = 0
    index = 1
    for i in range(1, n+1):
        for j in range(i):
            if index == n + 1:
                break
            max_element[index] = i
            index += 1
    for i in range(3, n+1):
        dp[i].append(max_element[i])
        for num in dp[i - max_element[i]]:
            dp[i].append(num)
    for ans in dp[n]:
        print(ans)

Submission Info

Submission Time
Task B - Exactly N points
User mobtake
Language PyPy3 (2.4.0)
Score 200
Code Size 2183 Byte
Status TLE
Exec Time 2142 ms
Memory 675024 KB

Judge Result

Set Name sample dataset1 dataset2
Score / Max Score 0 / 0 200 / 200 0 / 100
Status
AC × 3
AC × 13
AC × 16
TLE × 8
Set Name Test Cases
sample sample-01.txt, sample-02.txt, sample-03.txt
dataset1 sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt
dataset2 sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
01-01.txt AC 349 ms 69996 KB
01-02.txt AC 275 ms 65388 KB
01-03.txt AC 274 ms 65516 KB
01-04.txt AC 275 ms 65388 KB
01-05.txt AC 279 ms 66412 KB
01-06.txt AC 282 ms 66540 KB
01-07.txt AC 291 ms 66540 KB
01-08.txt AC 285 ms 66540 KB
01-09.txt AC 295 ms 66540 KB
01-10.txt AC 282 ms 66540 KB
02-01.txt TLE 2129 ms 641680 KB
02-02.txt TLE 2130 ms 657616 KB
02-03.txt TLE 2129 ms 661584 KB
02-04.txt TLE 2129 ms 652496 KB
02-05.txt TLE 2129 ms 642192 KB
02-06.txt TLE 2128 ms 523892 KB
02-07.txt TLE 2142 ms 656452 KB
02-08.txt TLE 2129 ms 675024 KB
sample-01.txt AC 276 ms 65388 KB
sample-02.txt AC 274 ms 65388 KB
sample-03.txt AC 274 ms 65388 KB