답안 #58202

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
58202 2018-07-17T06:46:20 Z 정원준(#1691) Candies (JOI18_candies) C++11
8 / 100
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 -