Submission #412982

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
412982	2021-05-27T22:36:09 Z	Chaska	Snowball (JOI21_ho_t2)	C++11	33 / 100	2500 ms	12108 KB

Main

#include <bits/stdc++.h> 
#define pb push_back
#define sp " "
#define sl "\n"
#define fi first
#define se second
#define mp make_pair
#define sz(a) ((int)a.size())
#define all(a) a.begin(),a.end()
#define rev(a) reverse(a.begin(),a.end())
#define PI 3.141592
#define fo(i,n) for (int i=0;i<n;i++)
#define fofo(i,n,j,m) for (int i=0;i<n;i++) for (int j=0;j<m;j++) 
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
const int N=2e5+5,mod=1e9+7;

ll n,q,a[N],w[N],acu,tam[N];
ll X[N],Y[N];
vector<pair<ll,ll>> group; // sortear por fi
ll res[N];

int main() { 
	cin.tie(0); cout.tie(0); 
	ios_base::sync_with_stdio();
	cin >> n >> q;
	fo(i,n) 
		cin >> a[i];
	fo(i,q) 
		cin >> w[i];
	ll x,y;
	x=y=0;
	fo(i,q) {
		acu += w[i];
		if (acu < x) x = acu;
		if (acu > y) y = acu;
		tam[i] = abs(x) + abs(y);
		
		X[i] = abs(x);
		Y[i] = abs(y);
  	}
	for (int i=0;i<n-1;i++) {
		ll p = a[i+1]-a[i];
		// tam del seg
		// do the bin ? 
		bool y = false;
		for (int j=0;j<q;j++) {
			if (tam[j]>=p) {
				if (j==0) {
					if (w[j]>=0)
					res[i] += p;
					else res[i+1] += p;
				} else {
					res[i] += Y[j-1];
					res[i+1] += X[j-1];
					p -= tam[j-1];
					if (w[j]>=0)
						res[i] += p;
					else 
						res[i+1] += p;
				}
				j = q+1;
				y = true;
			}
		}
		if (!y) {
			res[i] += Y[q-1];
			res[i+1] += X[q-1];
		}
	}
	res[0] += X[q-1];
	res[n-1] += Y[q-1];
	fo(i,n) cout << res[i] << "\n";
	return 0;
}
// Recuerda limites 
// Recuerda casos especiales

Subtask #1

33.0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	332 KB	Output is correct
2	Correct	2 ms	332 KB	Output is correct
3	Correct	2 ms	332 KB	Output is correct
4	Correct	5 ms	332 KB	Output is correct
5	Correct	5 ms	332 KB	Output is correct
6	Correct	4 ms	332 KB	Output is correct
7	Correct	4 ms	332 KB	Output is correct
8	Correct	4 ms	332 KB	Output is correct
9	Correct	4 ms	332 KB	Output is correct
10	Correct	4 ms	332 KB	Output is correct
11	Correct	4 ms	460 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	5 ms	332 KB	Output is correct
16	Correct	5 ms	332 KB	Output is correct
17	Correct	4 ms	332 KB	Output is correct
18	Correct	1 ms	332 KB	Output is correct
19	Correct	6 ms	332 KB	Output is correct

Subtask #2

0 / 67.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	332 KB	Output is correct
2	Correct	2 ms	332 KB	Output is correct
3	Correct	2 ms	332 KB	Output is correct
4	Correct	5 ms	332 KB	Output is correct
5	Correct	5 ms	332 KB	Output is correct
6	Correct	4 ms	332 KB	Output is correct
7	Correct	4 ms	332 KB	Output is correct
8	Correct	4 ms	332 KB	Output is correct
9	Correct	4 ms	332 KB	Output is correct
10	Correct	4 ms	332 KB	Output is correct
11	Correct	4 ms	460 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	5 ms	332 KB	Output is correct
16	Correct	5 ms	332 KB	Output is correct
17	Correct	4 ms	332 KB	Output is correct
18	Correct	1 ms	332 KB	Output is correct
19	Correct	6 ms	332 KB	Output is correct
20	Correct	89 ms	6468 KB	Output is correct
21	Correct	85 ms	6456 KB	Output is correct
22	Correct	95 ms	6572 KB	Output is correct
23	Correct	270 ms	6592 KB	Output is correct
24	Correct	1995 ms	7972 KB	Output is correct
25	Execution timed out	2586 ms	12108 KB	Time limit exceeded
26	Halted	0 ms	0 KB	-