Submission #1082302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082302		Halym2007	Closing Time (IOI23_closing)	C++17	0 / 100	1033 ms	13276 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], 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) {
					// i-dan j-cenli
					// l-dan r-cenli
					ll val = 0;
					if (j < l) {
						val = p[i] + p[j] + q[l] + q[r];
					}
					else {
						int res = max (l, i), res1 = min (r, j);
						val = jog[res1];
						if (res != 0) val -= jog[res - 1];
						val += p[i] + p[j] + q[l] + q[r];
						ll ayyr = 0;
						if (X <= res) {
							ayyr += p[res1];
							if (res > X) ayyr -= p[res];
						}
						else {
							ayyr += p[res1];
							ayyr += p[res];
						}
						ll ayyr1 = 0;
						if (Y >= res1) {
							ayyr1 += q[res];
							if (res1 < Y) ayyr1 -= q[res1 + 1];
						}
						else {
							ayyr1 += q[res1];
							ayyr1 += q[res];
						}
						val -= ayyr - ayyr1;
					}
//						if (i == 0 and j == 6 and l == 1 and r == 2) {
////							cout << val << " " << res << " " << res1;
////							cout << p[i] << " " << p[j] << " " << q[l] << " " << q[r];
//							cout << val;
//							exit(0);
//						}
					
					if (val <= K) {
						ret = max (ret, (X - i + 1) + (j - X) + (Y - l + 1) + (r - Y));
					}
//					if (ret == 9) {
//						cout << i << " " << j << " " << l << " " << r << " " << val << " " << K << "\n";
//						exit(0);
//					}
				}
			}
		}
	}
	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: 0 / 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