답안 #203668

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
203668	2020-02-21T19:25:24 Z	cheetose	Sparklers (JOI17_sparklers)	C++11	50 / 100	181 ms	16040 KB

sparklers

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define y0 y12
#define y1 y22
#define INF 987654321987654321
#define PI 3.141592653589793238462643383279502884
#define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
#define fdn(i,a,b,c) for(int (i)=(a);(i)>=(b);(i)-=(c))
#define MEM0(a) memset((a),0,sizeof(a));
#define MEM_1(a) memset((a),-1,sizeof(a));
#define ALL(a) a.begin(),a.end()
#define SYNC ios_base::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef pair<ld, ld> Pd;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<double> Vd;
typedef vector<Pi> VPi;
typedef vector<Pll> VPll;
typedef vector<Pd> VPd;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tuple<ll, ll, ll> LLL;
typedef vector<iii> Viii;
typedef vector<LLL> VLLL;
typedef complex<double> base;
const int MOD = 998244353;
ll POW(ll a, ll b, ll MMM = MOD) { ll ret = 1; for (; b; b >>= 1, a = (a*a) % MMM)if (b & 1)ret = (ret*a) % MMM; return ret; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { if (a == 0 || b == 0)return a + b; return a*(b / gcd(a, b)); }
int dx[] = { 0,1,0,-1,1,1,-1,-1 }, dy[] = { 1,0,-1,0,1,-1,1,-1 };

int n,k;
ll t,a[1000];
Pll d[1000][1000];
bool ok(ll m)
{
	fup(i,0,n-1,1)fup(j,0,n-1,1)d[i][j]=mp(INF,-INF);
	d[k][k]=mp(a[k],a[k]);
	fup(kk,1,n-1,1)
	{
		fup(i,0,n-1-kk,1)
		{
			int j=i+kk;
			if(d[i+1][j].X<=d[i+1][j].Y && d[i+1][j].X-t*m<=a[i]+t*m*kk)
			{
				d[i][j].X=min(d[i][j].X,max(d[i+1][j].X-t*m,a[i]-t*m*kk));
				d[i][j].Y=max(d[i][j].Y,min(d[i+1][j].Y+t*m,a[i]+t*m*kk));
			}
			if(d[i][j-1].X<=d[i][j-1].Y && d[i][j-1].Y+t*m>=a[j]-t*m*kk)
			{
				d[i][j].X=min(d[i][j].X,max(d[i][j-1].X-t*m,a[j]-t*m*kk));
				d[i][j].Y=max(d[i][j].Y,min(d[i][j-1].Y+t*m,a[j]+t*m*kk));
			}
		}
	}
	return d[0][n-1].X<=d[0][n-1].Y;
}
int main() {
	scanf("%d%d%lld",&n,&k,&t);k--;
	fup(i,0,n-1,1)scanf("%lld",a+i);
	ll l=0,r=1000000000;
	while(l<=r)
	{
		ll m=l+r>>1;
		if(ok(m))r=m-1;
		else l=m+1;
	}
	printf("%lld",l);
}

Compilation message

sparklers.cpp: In function 'int main()':
sparklers.cpp:75:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   ll m=l+r>>1;
        ~^~
sparklers.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%lld",&n,&k,&t);k--;
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:71:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  fup(i,0,n-1,1)scanf("%lld",a+i);
                ~~~~~^~~~~~~~~~~~

Subtask #1
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	5 ms	376 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct
4	Correct	5 ms	376 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	5 ms	376 KB	Output is correct
7	Correct	5 ms	376 KB	Output is correct
8	Correct	5 ms	376 KB	Output is correct
9	Correct	5 ms	376 KB	Output is correct
10	Correct	5 ms	376 KB	Output is correct
11	Correct	5 ms	376 KB	Output is correct
12	Correct	5 ms	380 KB	Output is correct
13	Correct	5 ms	376 KB	Output is correct
14	Correct	5 ms	376 KB	Output is correct
15	Correct	5 ms	376 KB	Output is correct
16	Correct	5 ms	376 KB	Output is correct
17	Correct	5 ms	376 KB	Output is correct
18	Correct	5 ms	376 KB	Output is correct
19	Correct	5 ms	376 KB	Output is correct
20	Correct	5 ms	376 KB	Output is correct
21	Correct	5 ms	376 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	5 ms	376 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct
4	Correct	5 ms	376 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	5 ms	376 KB	Output is correct
7	Correct	5 ms	376 KB	Output is correct
8	Correct	5 ms	376 KB	Output is correct
9	Correct	5 ms	376 KB	Output is correct
10	Correct	5 ms	376 KB	Output is correct
11	Correct	5 ms	376 KB	Output is correct
12	Correct	5 ms	380 KB	Output is correct
13	Correct	5 ms	376 KB	Output is correct
14	Correct	5 ms	376 KB	Output is correct
15	Correct	5 ms	376 KB	Output is correct
16	Correct	5 ms	376 KB	Output is correct
17	Correct	5 ms	376 KB	Output is correct
18	Correct	5 ms	376 KB	Output is correct
19	Correct	5 ms	376 KB	Output is correct
20	Correct	5 ms	376 KB	Output is correct
21	Correct	5 ms	376 KB	Output is correct
22	Correct	66 ms	11640 KB	Output is correct
23	Correct	40 ms	7672 KB	Output is correct
24	Correct	53 ms	11516 KB	Output is correct
25	Correct	104 ms	15996 KB	Output is correct
26	Correct	129 ms	16032 KB	Output is correct
27	Correct	135 ms	15992 KB	Output is correct
28	Correct	151 ms	15992 KB	Output is correct
29	Correct	139 ms	16036 KB	Output is correct
30	Correct	141 ms	15992 KB	Output is correct
31	Correct	141 ms	15992 KB	Output is correct
32	Correct	152 ms	15992 KB	Output is correct
33	Correct	149 ms	16036 KB	Output is correct
34	Correct	142 ms	15992 KB	Output is correct
35	Correct	149 ms	15992 KB	Output is correct
36	Correct	115 ms	16040 KB	Output is correct
37	Correct	142 ms	16032 KB	Output is correct
38	Correct	145 ms	15992 KB	Output is correct
39	Correct	120 ms	15992 KB	Output is correct
40	Correct	181 ms	15992 KB	Output is correct

Subtask #3
0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	5 ms	376 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct
4	Correct	5 ms	376 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	5 ms	376 KB	Output is correct
7	Correct	5 ms	376 KB	Output is correct
8	Correct	5 ms	376 KB	Output is correct
9	Correct	5 ms	376 KB	Output is correct
10	Correct	5 ms	376 KB	Output is correct
11	Correct	5 ms	376 KB	Output is correct
12	Correct	5 ms	380 KB	Output is correct
13	Correct	5 ms	376 KB	Output is correct
14	Correct	5 ms	376 KB	Output is correct
15	Correct	5 ms	376 KB	Output is correct
16	Correct	5 ms	376 KB	Output is correct
17	Correct	5 ms	376 KB	Output is correct
18	Correct	5 ms	376 KB	Output is correct
19	Correct	5 ms	376 KB	Output is correct
20	Correct	5 ms	376 KB	Output is correct
21	Correct	5 ms	376 KB	Output is correct
22	Correct	66 ms	11640 KB	Output is correct
23	Correct	40 ms	7672 KB	Output is correct
24	Correct	53 ms	11516 KB	Output is correct
25	Correct	104 ms	15996 KB	Output is correct
26	Correct	129 ms	16032 KB	Output is correct
27	Correct	135 ms	15992 KB	Output is correct
28	Correct	151 ms	15992 KB	Output is correct
29	Correct	139 ms	16036 KB	Output is correct
30	Correct	141 ms	15992 KB	Output is correct
31	Correct	141 ms	15992 KB	Output is correct
32	Correct	152 ms	15992 KB	Output is correct
33	Correct	149 ms	16036 KB	Output is correct
34	Correct	142 ms	15992 KB	Output is correct
35	Correct	149 ms	15992 KB	Output is correct
36	Correct	115 ms	16040 KB	Output is correct
37	Correct	142 ms	16032 KB	Output is correct
38	Correct	145 ms	15992 KB	Output is correct
39	Correct	120 ms	15992 KB	Output is correct
40	Correct	181 ms	15992 KB	Output is correct
41	Runtime error	7 ms	632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
42	Halted	0 ms	0 KB	-

답안 #203668

Compilation message

Subtask #1 30.0 / 30.0

Subtask #2 20.0 / 20.0

Subtask #3 0 / 50.0

Subtask #1
30.0 / 30.0

Subtask #2
20.0 / 20.0

Subtask #3
0 / 50.0