| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1006890 |
2024-06-24T09:35:26 Z |
Amr |
Closing Time (IOI23_closing) |
C++17 |
|
1000 ms |
12784 KB |
// start at :10:36
#include "closing.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define sz size()
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef long double ld;
const int M = 2e5+3;
ll n , k;
ll disx[M], disy[M] , ansx[M], ansy[M],prex[M];
int max_score(int N, int X, int Y, long long K,
std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
// it's chain
n = N , k = K;
for(int i = 0; i <= n; i++) disx[i] = disy[i] = ansx[i] = ansy[i] = prex[i] = 0;
ll mainbest = 0;
if(X>Y) swap(X,Y);
ll x = X , y = Y;
for(int i = x+1; i < n; i++) disx[i] = disx[i-1]+W[i-1];
for(int i = x-1; i >= 0; i--) disx[i] = disx[i+1]+W[i];
for(int i = y+1; i < n; i++) disy[i] = disy[i-1]+W[i-1];
for(int i = y-1; i>=0; i--) disy[i] = disy[i+1]+W[i];
for(int i = x-1; i >= 0; i--) prex[i] = prex[i+1]+disx[i];
ll tailx = X , taily = Y, sum = 0;
while(sum<=k)
{
// make brute force
ll fx = min(x-1,taily-1), fy = max(y+1,tailx+1);
ll bestx = 0, dif = k-sum,besty = 0,best = 0;
for(int i = fy; i < n ;i++) if(dif>=disy[i]) dif-=disy[i],besty++; else break;
dif = k -sum;
for(int i = fx; i >= 0; i--) if(dif>=disx[i]) dif-=disx[i],bestx++; else break;
ll both = ((taily<x)*(x-taily)) + ((tailx>y)*(tailx-y));
best = max(besty,bestx)+both;
dif = k-sum;
for(int i = fy; i < n ;i++)
{
dif-=disy[i];
ll our = 0;
ll l = -1 , r = fx+1;
while(l+1<r)
{
ll mid = (l+r)/2;
if(prex[mid]-prex[fx+1]<=dif) r = mid; else l = mid;
}
if(r!=fx+1);
best = max(best,i-y+x-r);
/*for(int j = fx; j >= 0; j--)
{
our+=disx[j];
if(dif-our>=0) best = max(best,i-y+x-j);
}*/
}
mainbest = max(mainbest,best+tailx-x+1+y-taily+1);
// cout << tailx << " " << taily << " " << sum << " " << best << " " << mainbest << " " << tailx-x+1+y-taily+1 << endl;
if(taily==0&&tailx==n-1) break;
// rise the sum
if(taily==0)
{
sum+=disx[tailx+1]-ansy[tailx+1];
ansx[tailx+1] = disx[tailx+1];
tailx++;
}
else if(tailx==n-1)
{
sum+=disy[taily-1]-ansx[taily-1];
ansy[taily-1] = disy[taily-1];
taily--;
}
else
{
if(disx[tailx+1]-ansy[tailx+1] < disy[taily-1]-ansx[taily-1])
{
sum+=disx[tailx+1]-ansy[tailx+1];
ansx[tailx+1] = disx[tailx+1];
tailx++;
}
else
{
sum+=disy[taily-1]-ansx[taily-1];
ansy[taily-1] = disy[taily-1];
taily--;
}
}
}
return mainbest;
}
Compilation message
closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:45:16: warning: unused variable 'our' [-Wunused-variable]
45 | ll our = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6492 KB |
1st lines differ - on the 1st token, expected: '6', found: '9' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1086 ms |
12784 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6492 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6492 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6492 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6492 KB |
1st lines differ - on the 1st token, expected: '6', found: '9' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6492 KB |
1st lines differ - on the 1st token, expected: '6', found: '9' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6492 KB |
1st lines differ - on the 1st token, expected: '6', found: '9' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6492 KB |
1st lines differ - on the 1st token, expected: '6', found: '9' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6492 KB |
1st lines differ - on the 1st token, expected: '6', found: '9' |
| 2 |
Halted |
0 ms |
0 KB |
- |
