oj.uz

Submission #667152

# Submission time Handle Problem Language Result Execution time Memory
667152 2022-11-30T13:15:45 Z flappybird Toll (BOI17_toll) C++17
7 / 100
 328 ms 259348 KB 
#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 50505
#define MAXS 17
#define INF 10000000000000
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MK 5
vector<vector<ll>> sp[MAX][MAXS];
int K;
vector<vector<ll>> operator+(vector<vector<ll>>& v1, vector<vector<ll>>& v2) {
	vector<vector<ll>> res = vector<vector<ll>>(K, vector<ll>(K, INF));
	int i, j, k;
	for (i = 0; i < K; i++) for (j = 0; j < K; j++) for (k = 0; k < K; k++) res[i][j] = min(res[i][j], v1[i][k] + v2[k][j]);
	return res;
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N, M, Q;
	cin >> K >> N >> M >> Q;
	int i, j;
	int X = (N + K - 1) / K;
	for (i = 0; i < MAX; i++) for (j = 0; j < MAXS; j++) sp[i][j] = vector<vector<ll>>(K, vector<ll>(K, INF));
	int a, b, c;
	for (i = 1; i <= M; i++) {
		cin >> a >> b >> c;
		sp[a / K][0][a % K][b % K] = c;
	}
	for (j = 1; j < MAXS; j++) for (i = 0; i <= X; i++) if (i + (1 << (j - 1)) <= X + 1) sp[i][j] = sp[i][j - 1] + sp[i + (1 << (j - 1))][j - 1];
	while (Q--) {
		cin >> a >> b;
		int aa = a;
		int d = b / K - a / K;
		a /= K;
		vector<vector<ll>> v;
		for (i = 0; i < MAXS; i++) {
			if (d >> i & 1) {
				if (v.empty()) v = sp[a][i];
				else v = v + sp[a][i];
				a += 1 << i;
			}
		}
		ll ans = v[aa % K][b % K];
		if (ans >= INF) cout << -1 << ln;
		else cout << ans << ln;
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 74308 KB Output is correct
2 Correct 106 ms 74336 KB Output is correct
3 Correct 102 ms 74152 KB Output is correct
4 Correct 101 ms 74168 KB Output is correct
5 Correct 103 ms 74228 KB Output is correct
6 Correct 103 ms 74204 KB Output is correct
7 Correct 131 ms 74164 KB Output is correct
8 Correct 213 ms 74340 KB Output is correct
9 Correct 213 ms 74148 KB Output is correct
10 Correct 197 ms 74192 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 127996 KB Output is correct
2 Correct 102 ms 74116 KB Output is correct
3 Runtime error 231 ms 259348 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 74120 KB Output is correct
2 Runtime error 231 ms 259300 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 74120 KB Output is correct
2 Runtime error 231 ms 259300 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 74308 KB Output is correct
2 Correct 106 ms 74336 KB Output is correct
3 Correct 102 ms 74152 KB Output is correct
4 Correct 101 ms 74168 KB Output is correct
5 Correct 103 ms 74228 KB Output is correct
6 Correct 103 ms 74204 KB Output is correct
7 Correct 131 ms 74164 KB Output is correct
8 Correct 213 ms 74340 KB Output is correct
9 Correct 213 ms 74148 KB Output is correct
10 Correct 197 ms 74192 KB Output is correct
11 Correct 328 ms 127996 KB Output is correct
12 Correct 102 ms 74116 KB Output is correct
13 Runtime error 231 ms 259348 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -