oj.uz

Submission #842409

# Submission time Handle Problem Language Result Execution time Memory
842409 2023-09-02T20:41:25 Z omeganot Closing Time (IOI23_closing) C++17
0 / 100
 1000 ms 897252 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const int MOD = 1E9 + 7;
const int INF = 1E9; const ll INFLL = 1E18;

int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W) {
	vector<int> w(N);
	for(int i = 0; i + 1 < N; i++) {
		w[min(U[i], V[i])] = W[i];
	}
	vector<ll> wX(N); vector<ll> wY(N);
	for(int i = X + 1; i < N; i++) {
		wX[i] = wX[i - 1] + w[i];
	}
	for(int i = X - 1; i >= 0; i--) {
		wX[i] = wX[i + 1] + w[i];
	}
	for(int i = Y + 1; i < N; i++) {
		wY[i] = wY[i - 1] + w[i];
	}
	for(int i = Y - 1; i >= 0; i--) {
		wY[i] = wY[i + 1] + w[i];
	}
	vector<vector<array<ll, 9>>> dp(N, vector<array<ll, 9>>(2 * N + 1, {INFLL, INFLL, INFLL, INFLL, INFLL, INFLL, INFLL, INFLL, INFLL}));
	dp[0][0][0] = 0; dp[0][1][1] = wY[0]; 
	dp[0][1][3] = wX[0]; dp[0][2][4] = wX[0] + wY[0];
	for(int i = 1; i < N; i++) {
		for(int j = 0; j <= i * 2; j++) {
			if(!j) {
				dp[i][j][0] = 0;
			}
			dp[i][j + 1][1] = min(dp[i][j + 1][1], min((i <= Y ? dp[i - 1][j][0] : INFLL), dp[i - 1][j][1]) + wY[i]);
			if(i >= Y) {
				dp[i][j][2] = min({dp[i][j][2], dp[i - 1][j][1], dp[i - 1][j][2]});
				dp[i][j + 1][5] = min(dp[i][j + 1][5], min({(i <= X ? min(dp[i - 1][j][1], dp[i - 1][j][2]) : INFLL), dp[i - 1][j][4], dp[i - 1][j][5]}) + wX[i]);
			}
			dp[i][j + 1][3] = min(dp[i][j + 1][3], min((i <= X ? dp[i - 1][j][0] : INFLL), dp[i - 1][j][3]) + wX[i]);
			dp[i][j + 2][4] = min(dp[i][j + 2][4], min({(i <= min(X, Y) ? dp[i - 1][j][0] : INFLL), (i <= X ? dp[i - 1][j][1] : INFLL), (i <= Y ? dp[i - 1][j][3] : INFLL), dp[i - 1][j][4]}) + max(wX[i], wY[i]));
			if(i >= X) {
				dp[i][j][6] = min({dp[i][j][6], dp[i - 1][j][3], dp[i - 1][j][6]});
				dp[i][j + 1][7] = min(dp[i][j + 1][7], min({(i <= Y ? min(dp[i - 1][j][3], dp[i - 1][j][6]) : INFLL), dp[i - 1][j][4], dp[i - 1][j][7]}) + wY[i]);
				if(i >= Y) {
					dp[i][j][8] = min({dp[i][j][8], dp[i - 1][j][4], dp[i - 1][j][5], dp[i - 1][j][7], dp[i - 1][j][8]});
				}
			}
		}
	}
	for(int i = N * 2; i >= 2; i--) {
		if(min({dp[N - 1][i][4], dp[N - 1][i][5], dp[N - 1][i][7], dp[N - 1][i][8]}) <= K) {
			return i;
		}
	}
}

Compilation message

closing.cpp: In function 'int max_score(int, int, int, ll, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:10:17: warning: control reaches end of non-void function [-Wreturn-type]
   10 |  vector<int> w(N);
      |                 ^

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '6', found: '8'
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1046 ms 897252 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '6', found: '8'
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '6', found: '8'
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '6', found: '8'
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '6', found: '8'
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '6', found: '8'
2 Halted 0 ms 0 KB -