oj.uz

Submission #958287

# Submission time Handle Problem Language Result Execution time Memory
958287 2024-04-05T10:13:00 Z lovrot Super Dango Maker (JOI22_dango3) C++17
100 / 100
 262 ms 1104 KB 
#include "dango3.h"
#include <vector>
#include <cstdio>
#include <algorithm> 

using namespace std;

const int MAXN = 30;
const int OO = 2e9;

int DP[MAXN], I[MAXN];

void dnc(vector<int> V, int n) {
	if(n == 1) {
		Answer(V);
		return;
	}
	
	vector<int> _V;
	for(int i = (int) V.size() - 1; i >= 0; --i) {
		int x = V[i];
		V.erase(V.begin() + i); 
		if(Query(V) >= I[n]) _V.push_back(x);
		else V.push_back(x);
	}
	
	dnc(V, I[n]);
	dnc(_V, n - I[n]);
}

void Solve(int N, int M) {
	DP[1] = 0;
	for(int i = 2; i <= M; ++i) {
		DP[i] = OO;
		for(int j = 1; j < i; ++j) 
			if(DP[i] > DP[j] + DP[i - j] + i) {
				DP[i] = DP[j] + DP[i - j] + i;
				I[i] = j;
			}
	}

	vector<int> V;
	for(int i = 1; i <= N * M; ++i) V.push_back(i);
	dnc(V, M);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 596 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 3 ms 348 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 588 KB Output is correct
2 Correct 48 ms 568 KB Output is correct
3 Correct 66 ms 576 KB Output is correct
4 Correct 66 ms 588 KB Output is correct
5 Correct 47 ms 596 KB Output is correct
6 Correct 49 ms 600 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 656 KB Output is correct
2 Correct 187 ms 712 KB Output is correct
3 Correct 262 ms 672 KB Output is correct
4 Correct 260 ms 632 KB Output is correct
5 Correct 182 ms 676 KB Output is correct
6 Correct 183 ms 1104 KB Output is correct