| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 58202 |
2018-07-17T06:46:20 Z |
정원준(#1691) |
Candies (JOI18_candies) |
C++11 |
|
108 ms |
10400 KB |
#include <bits/stdc++.h>
#define L long long
using namespace std;
L n,ans;
L a[100010],nex[100010],pre[100010],cd[100010];
struct S{
L val,loc,candy;
};
bool operator<(S a,S b){
if(a.val==b.val) return a.loc<b.loc;
return a.val>b.val;
}
bool operator==(S a,S b){
return a.val==b.val&&a.loc==b.loc;
}
set<S>st;
int main()
{
scanf("%lld",&n);
L i,j;
for(i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
nex[i]=i+1;
pre[i]=i-1;
cd[i]=1;
S temp=(S){a[i],i,1};
st.insert(temp);
}
nex[0]=1;
pre[0]=0;
nex[n+1]=n+1;
pre[n+1]=n;
/*for(set<S>::iterator ii=st.begin();ii!=st.end();ii++)
{
printf("%lld %lld\n",ii->loc,ii->val);
}
for(j=1;j<=n;j++)
{
printf("%lld ",nex[j]);
}
puts("");
for(j=1;j<=n;j++)
{
printf("%lld ",pre[j]);
}
puts("");*/
for(i=1;i<=(n+1)/2;i++)
{
set<S>::iterator now=st.begin();
ans+=now->val;
if(pre[now->loc]==0&&nex[now->loc]==n+1)
{
st.erase(now);
}
else if(pre[now->loc]==0)
{
//puts("1");
S nextemp=(S){a[nex[now->loc]],nex[now->loc],cd[nex[now->loc]]};
S inptemp=(S){nextemp.val-a[now->loc],now->loc,nextemp.candy-now->candy};
a[now->loc]=nextemp.val-a[now->loc];
cd[now->loc]=nextemp.candy-now->candy;
pre[nex[nex[now->loc]]]=pre[now->loc];
nex[now->loc]=nex[nex[now->loc]];
st.erase(now);
st.erase(nextemp);
//st.insert(inptemp);
}
else if(nex[now->loc]==n+1)
{
//puts("2");
S pretemp=(S){a[pre[now->loc]],pre[now->loc],cd[pre[now->loc]]};
S inptemp=(S){pretemp.val-a[now->loc],now->loc,pretemp.candy-now->candy};
a[now->loc]=pretemp.val-a[now->loc];
cd[now->loc]=pretemp.candy-now->candy;
nex[pre[pre[now->loc]]]=nex[now->loc];
pre[now->loc]=pre[pre[now->loc]];
st.erase(now);
st.erase(pretemp);
//st.insert(inptemp);
}
else
{
//puts("3");
S nextemp=(S){a[nex[now->loc]],nex[now->loc],cd[nex[now->loc]]};
S pretemp=(S){a[pre[now->loc]],pre[now->loc],cd[pre[now->loc]]};
S inptemp=(S){nextemp.val+pretemp.val-a[now->loc],now->loc,nextemp.candy+pretemp.candy-now->candy};
a[now->loc]=nextemp.val+pretemp.val-a[now->loc];
cd[now->loc]=nextemp.candy+pretemp.candy-now->candy;
/*printf("%lld %lld\n",nextemp.loc,nextemp.val);
printf("%lld %lld\n",pretemp.loc,pretemp.val);
printf("%lld %lld\n",inptemp.loc,inptemp.val);*/
pre[nex[nex[now->loc]]]=now->loc;
nex[now->loc]=nex[nex[now->loc]];
nex[pre[pre[now->loc]]]=now->loc;
pre[now->loc]=pre[pre[now->loc]];
st.erase(now);
st.erase(nextemp);
st.erase(pretemp);
st.insert(inptemp);
}
printf("%lld\n",ans);
//printf("**%lld**\n",ans);
/*for(set<S>::iterator ii=st.begin();ii!=st.end();ii++)
{
printf("%lld %lld\n",ii->loc,ii->val);
}
for(j=1;j<=n;j++)
{
printf("%lld ",nex[j]);
}
puts("");
for(j=1;j<=n;j++)
{
printf("%lld ",pre[j]);
}
puts("");
for(j=1;j<=n;j++)
{
printf("%lld ",cd[j]);
}
puts("");*/
}
}
Compilation message
candies.cpp: In function 'int main()':
candies.cpp:69:6: warning: variable 'inptemp' set but not used [-Wunused-but-set-variable]
S inptemp=(S){nextemp.val-a[now->loc],now->loc,nextemp.candy-now->candy};
^~~~~~~
candies.cpp:84:6: warning: variable 'inptemp' set but not used [-Wunused-but-set-variable]
S inptemp=(S){pretemp.val-a[now->loc],now->loc,pretemp.candy-now->candy};
^~~~~~~
candies.cpp:27:6: warning: unused variable 'j' [-Wunused-variable]
L i,j;
^
candies.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&n);
~~~~~^~~~~~~~~~~
candies.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&a[i]);
~~~~~^~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
504 KB |
Output is correct |
| 2 |
Correct |
6 ms |
612 KB |
Output is correct |
| 3 |
Correct |
4 ms |
852 KB |
Output is correct |
| 4 |
Correct |
4 ms |
852 KB |
Output is correct |
| 5 |
Correct |
4 ms |
924 KB |
Output is correct |
| 6 |
Correct |
4 ms |
924 KB |
Output is correct |
| 7 |
Correct |
5 ms |
924 KB |
Output is correct |
| 8 |
Correct |
4 ms |
1088 KB |
Output is correct |
| 9 |
Correct |
4 ms |
1088 KB |
Output is correct |
| 10 |
Correct |
6 ms |
1088 KB |
Output is correct |
| 11 |
Correct |
4 ms |
1088 KB |
Output is correct |
| 12 |
Correct |
5 ms |
1132 KB |
Output is correct |
| 13 |
Correct |
6 ms |
1132 KB |
Output is correct |
| 14 |
Correct |
5 ms |
1132 KB |
Output is correct |
| 15 |
Correct |
4 ms |
1132 KB |
Output is correct |
| 16 |
Correct |
5 ms |
1132 KB |
Output is correct |
| 17 |
Correct |
4 ms |
1132 KB |
Output is correct |
| 18 |
Correct |
4 ms |
1132 KB |
Output is correct |
| 19 |
Correct |
4 ms |
1132 KB |
Output is correct |
| 20 |
Correct |
5 ms |
1132 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
504 KB |
Output is correct |
| 2 |
Correct |
6 ms |
612 KB |
Output is correct |
| 3 |
Correct |
4 ms |
852 KB |
Output is correct |
| 4 |
Correct |
4 ms |
852 KB |
Output is correct |
| 5 |
Correct |
4 ms |
924 KB |
Output is correct |
| 6 |
Correct |
4 ms |
924 KB |
Output is correct |
| 7 |
Correct |
5 ms |
924 KB |
Output is correct |
| 8 |
Correct |
4 ms |
1088 KB |
Output is correct |
| 9 |
Correct |
4 ms |
1088 KB |
Output is correct |
| 10 |
Correct |
6 ms |
1088 KB |
Output is correct |
| 11 |
Correct |
4 ms |
1088 KB |
Output is correct |
| 12 |
Correct |
5 ms |
1132 KB |
Output is correct |
| 13 |
Correct |
6 ms |
1132 KB |
Output is correct |
| 14 |
Correct |
5 ms |
1132 KB |
Output is correct |
| 15 |
Correct |
4 ms |
1132 KB |
Output is correct |
| 16 |
Correct |
5 ms |
1132 KB |
Output is correct |
| 17 |
Correct |
4 ms |
1132 KB |
Output is correct |
| 18 |
Correct |
4 ms |
1132 KB |
Output is correct |
| 19 |
Correct |
4 ms |
1132 KB |
Output is correct |
| 20 |
Correct |
5 ms |
1132 KB |
Output is correct |
| 21 |
Execution timed out |
108 ms |
10400 KB |
Time limit exceeded (wall clock) |
| 22 |
Halted |
0 ms |
0 KB |
- |
