| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1015259 |
2024-07-06T08:05:54 Z |
김은성(#10845) |
Shortcut (IOI16_shortcut) |
C++14 |
|
0 ms |
348 KB |
#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll p[200009];
ll dist[1009][1009];
ll temp[1009], suf[1009];
const ll INF = 0x3fffffffffffffffll;
long long find_shortcut2(int n, std::vector<int> L, std::vector<int> d, int c)
{
int i, j, k, l;
for(i=0; i<n; i++){
for(j=0; j<n; j++){
dist[i][j] = INF;
if(i==j)
dist[i][j] = 0;
}
}
for(i=0; i<n-1; i++){
dist[i][i+1] = dist[i+1][i] = L[i];
}
for(k=0; k<n; k++){
for(i=0; i<n; i++){
for(j=0; j<n; j++){
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
ll ans = INF;
for(k=0; k<n; k++){
for(l=k+1; l<n; l++){
ll cur = 0;
for(i=0; i<n; i++){
for(j=i+1; j<n; j++){
cur = max(cur, min(dist[i][j], min(dist[i][k] + dist[l][j] + c, dist[i][l] + dist[j][k] + c)) + d[i]+d[j]);
}
}
//if(cur < 200000)
// printf("k=%d l=%d\n", k, l);
ans = min(ans, cur);
}
}
return ans;
}
long long find_shortcut(int n, std::vector<int> L, std::vector<int> d, int c)
{
int i, j, k, l;
for(i=0; i<n-1; i++){
p[i+1] = p[i] + L[i];
}
ll ans = INF, org = 0;
temp[0] = d[0];
for(i=1; i<n; i++){
temp[i] = temp[i-1];
for(j=0; j<i; j++){
temp[i] = max(temp[i], p[i]-p[j] + d[i]+d[j]);
}
}
suf[n-1] = d[n-1];
for(i=n-2; i>=0; i--){
suf[i ]= suf[i+1];
for(j=i+1; j<n; j++){
suf[i] = max(suf[i], p[j]-p[i] + d[i]+d[j]);
}
}
for(i=0; i<n; i++){
for(j=i+1; j<n; j++){
org = max(org, p[j]+d[j] - p[i]+d[i]);
org = max(org, (ll)d[i]);
}
}
ans = org;
for(k=0; k<n; k++){
for(l=k+1; l<n; l++){
ll cur = 0;
int j = k;
ll mx = p[k] + d[k];
for(i=0; i<n; i++)
cur = max(cur, (ll)d[i]);
for(i=k; i<=l; i++){
while(j<l && p[j+1]-p[i] < c + p[l]+p[i]-p[k]-p[j+1]){
j++;
mx = max(mx, p[j] + d[j]);
}
mx = -INF;
for(int t=i+1; t<=j; t++){
mx = max(mx, p[t] + d[t]);
}
// printf("i=%d j=%d mx=%lld p[i]=%d d[i]=%d\n", i, j, mx, p[i], d[i]);
cur = max(cur, mx - p[i] + d[i]);
}
j = l+1;
mx = -INF;
for(i=l; i>=k; i--){
while(j>k && p[j-1]-p[i] >= c + p[l]+p[i]-p[k]-p[j-1]){
j--;
mx = max(mx, d[j] - p[j]);
}
mx = -INF;
for(int t=i+1; t<=j; t++){
mx = max(mx, d[t] - p[t]);
}
if(j<=i)
continue;
// printf("i=%d j=%d\n", i, j);
cur = max(cur, c + p[l] + p[i] + d[i] - p[k] + mx);
}
//printf("cur=%lld\n", cur);
mx = -INF;
for(i=0; i<k; i++){
mx = max(mx, d[i] - p[i]);
}
for(j=k; j<=l; j++){
cur = max(cur,mx + d[j] + min(p[j], c + p[l] + p[k] - p[j]));
}
ll mx2 = -INF;
for(j=l+1; j<n; j++){
mx2 = max(mx2, d[j] + p[j]);
}
for(i=k; i<=l; i++){
cur = max(cur, mx2+d[i] + min(-p[i], -p[l]-p[k]+p[i]+c));
}
mx = max(mx, d[k]-p[k]);
mx2 = max(mx2, d[l]+p[l]);
cur = max(cur, mx + mx2 - p[l] + p[k] + c);
cur = max(cur, temp[k]);
cur = max(cur, suf[l]);
//printf("k=%d l=%d cur=%lld\n", k, l, cur);
ans = min(ans, cur);
}
}
//long long t2 = find_shortcut2(n, L, d, c);
//printf("t2=%lld\n", t2);
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
n = 4, incorrect answer: jury 80 vs contestant 100 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
n = 4, incorrect answer: jury 80 vs contestant 100 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
n = 4, incorrect answer: jury 80 vs contestant 100 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
n = 4, incorrect answer: jury 80 vs contestant 100 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
n = 4, incorrect answer: jury 80 vs contestant 100 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
n = 4, incorrect answer: jury 80 vs contestant 100 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
n = 4, incorrect answer: jury 80 vs contestant 100 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
n = 4, incorrect answer: jury 80 vs contestant 100 |
| 2 |
Halted |
0 ms |
0 KB |
- |
