Submission #593389

#	Time	Username	Problem	Language	Result	Execution time	Memory
593389		haojiandan	Remittance (JOI19_remittance)	C++14	100 / 100	295 ms	59856 KiB

remittance

// wygzgyw
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
template <typename T> void write(T t) {
	if (t<0) { putchar('-'); write(-t); return; }
	if (t>9) write(t/10);
	putchar('0'+t%10);
}
template <typename T> void writeln(T t) { write(t); puts(""); }
#define MP make_pair
typedef long long ll;
const int maxn=(1e6)+10;
int n;
ll a[maxn],b[maxn],c[maxn];
struct node {
	ll x,y;
	friend node operator * (node A,ll B) { A.x*=B,A.y*=B; return A; }
} d[maxn];
int main() {
	read(n);
	for (int i=0;i<n;i++) read(a[i]),read(b[i]);
	d[n-1].x=2,d[n-1].y=b[0]-a[0];
	for (int i=n-2;i>=0;i--) {
		d[i]=(d[i+1]*2);
		d[i].y+=b[i+1]-a[i+1];
	}
	if (abs(d[0].y)%abs(1-d[0].x)!=0) { puts("No"); return 0; }
	c[0]=d[0].y/(1-d[0].x);
	if (c[0]<0) { puts("No"); return 0; }
	for (int i=1;i<n;i++) {
		c[i]=d[i].x*c[0]+d[i].y;
		if (c[i]<0) { puts("No"); return 0; }
	}
	for (int rd=0;rd<=40;rd++) {
		for (int i=0;i<n;i++) if (c[i]) {
			ll mn=min(a[i]/2,c[i]);
			a[i]-=mn*2,c[i]-=mn,a[(i+1)%n]+=mn;
		}
	}
	for (int i=0;i<n;i++) if (c[i]) { puts("No"); return 0; }
	puts("Yes");
	return 0;
}
/*
  0. Enough array size? Enough array size? Enough array size? Integer overflow?
  
  1. Think TWICE, Code ONCE!
  Are there any counterexamples to your algo?
    
  2. Be careful about the BOUNDARIES!
  N=1? P=1? Something about 0?
    
  3. Do not make STUPID MISTAKES!
  Time complexity? Memory usage? Precision error?
*/

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 45 / 45