Submission #1082304

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082304		Halym2007	Closing Time (IOI23_closing)	C++17	9 / 100	1098 ms	11348 KiB

closing

#include <bits/stdc++.h>
#include "closing.h"
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <int, int>
const int N = 2e5 + 5;
ll p[N], vis[N], q[N], jog[N];
int n;
int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) {
	n = N;
//	for (int i = 0; i < N - 1; ++i) {
//		v[U[i]].pb ({V[i], W[i]});
//		v[V[i]].pb ({U[i], W[i]});
//	}
//	return 1;
	ll sum = 0;
	for (int i = X + 1; i < N; ++i) {
		// 
		sum += W[i - 1];
		p[i] = sum;
	}
	sum = 0;
	for (int i = X - 1; i >= 0; i--) {
		sum += W[i];
		p[i] = sum;
	}
	
	sum = 0;
	for (int i = Y + 1; i < N; ++i) {
		// 
		sum += W[i - 1];
		q[i] = sum;
	}
	sum = 0;
	for (int i = Y - 1; i >= 0; i--) {
		sum += W[i];
		q[i] = sum;
	}
	
//	exit(0);
	for (int i = 0; i < n; ++i) {
		jog[i] = max (q[i], p[i]);
	}
//	for (int i = 0; i < n; ++i) {
//		cout << p[i] << " ";
//	}
//	cout << "\n";
//	for (int i = 0; i < n; ++i) {
//		cout << q[i] << " ";
//	}
//	cout << "\n";
//	for (int i = 0; i < n; ++i) {
//		cout << jog[i] << " ";
//	}
//	exit(0);
	for (int i = 1; i < n; ++i) {
		jog[i] += jog[i - 1];
	}
	int ret = 0;
	for (int i = 0; i <= X; ++i) {
		for (int j = X; j < n; ++j) {
			for (int l = 0; l <= Y; ++l) {
				for (int r = Y; r < n; ++r) {
					for (int k = 0; k < n; ++k) {
						vis[k] = -1;
					}
					for (int k = i; k <= j; ++k) {
						vis[k] = p[k];
					}
					for (int k = l; k <= r; ++k) {
						if (vis[k] == -1) {
							vis[k] = q[k];
						}
						else {
							vis[k] = max (vis[k], q[k]);
						}
					}
					ll val = 0;
					for (int k = 0; k < n; ++k) {
						if (~vis[k]) val += vis[k];
					}
					if (val <= K) {
						ret = max (ret, (X - i + 1) + (j - X) + (Y - l + 1) + (r - Y));
					}
				}
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		p[i] = q[i] = jog[i] = 0;
	}
    return ret;
}

//int main() {
//	freopen ("input.txt", "r", stdin);
//	
////	cout << max_score(7, 0, 2, 10, [0, 0, 1, 2, 2, 5], [1, 3, 2, 4, 5, 6], [2, 3, 4, 2, 5, 3]);
//	
//    int Q;
//    assert(1 == scanf("%d", &Q));
//
//    std::vector<int> N(Q), X(Q), Y(Q);
//    std::vector<long long> d, K(Q);
//    std::vector<std::vector<int>> U(Q), V(Q), W(Q);
//
//    for (int q = 0; q < Q; q++)
//    {
//        assert(4 == scanf("%d %d %d %lld", &N[q], &X[q], &Y[q], &K[q]));
//
//        U[q].resize(N[q] - 1);
//        V[q].resize(N[q] - 1);
//        W[q].resize(N[q] - 1);
//        for (int i = 0; i < N[q] - 1; ++i)
//        {
//            assert(3 == scanf("%d %d %d", &U[q][i], &V[q][i], &W[q][i]));
//        }
//    }
//    fclose(stdin);
//
//    std::vector<int> result(Q);
//    for (int q = 0; q < Q; q++)
//    {
//        result[q] = max_score(N[q], X[q], Y[q], K[q], U[q], V[q], W[q]);
//    }
//
//    for (int q = 0; q < Q; q++)
//    {
//        printf("%d\n", result[q]);
//    }
//    fclose(stdout);
//
//    return 0;
//}
/*
2
7 0 2 10
0 1 2
0 3 3
1 2 4
2 4 2
2 5 5
5 6 3
4 0 3 20
0 1 18
1 2 1
2 3 19

answer : 6 3
*/

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 9 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17