oj.uz

Submission #667147

# Submission time Handle Problem Language Result Execution time Memory
667147 2022-11-30T13:07:55 Z flappybird Toll (BOI17_toll) C++17
7 / 100
 488 ms 518352 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 101010
#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, k, l;
	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++) 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;
	}
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:38:95: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   38 |  for (j = 1; j < MAXS; j++) for (i = 0; i <= X; i++) sp[i][j] = sp[i][j - 1] + sp[i + (1 << j - 1)][j - 1];
      |                                                                                             ~~^~~
toll.cpp:30:12: warning: unused variable 'k' [-Wunused-variable]
   30 |  int i, j, k, l;
      |            ^
toll.cpp:30:15: warning: unused variable 'l' [-Wunused-variable]
   30 |  int i, j, k, l;
      |               ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 149164 KB Output is correct
2 Correct 196 ms 148076 KB Output is correct
3 Correct 208 ms 148148 KB Output is correct
4 Correct 190 ms 148152 KB Output is correct
5 Correct 198 ms 148064 KB Output is correct
6 Correct 201 ms 148112 KB Output is correct
7 Correct 222 ms 148088 KB Output is correct
8 Correct 303 ms 149108 KB Output is correct
9 Correct 322 ms 149072 KB Output is correct
10 Correct 294 ms 148308 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 257368 KB Output is correct
2 Correct 198 ms 148076 KB Output is correct
3 Runtime error 488 ms 518204 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 215 ms 148088 KB Output is correct
2 Runtime error 463 ms 518352 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 215 ms 148088 KB Output is correct
2 Runtime error 463 ms 518352 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 311 ms 149164 KB Output is correct
2 Correct 196 ms 148076 KB Output is correct
3 Correct 208 ms 148148 KB Output is correct
4 Correct 190 ms 148152 KB Output is correct
5 Correct 198 ms 148064 KB Output is correct
6 Correct 201 ms 148112 KB Output is correct
7 Correct 222 ms 148088 KB Output is correct
8 Correct 303 ms 149108 KB Output is correct
9 Correct 322 ms 149072 KB Output is correct
10 Correct 294 ms 148308 KB Output is correct
11 Correct 440 ms 257368 KB Output is correct
12 Correct 198 ms 148076 KB Output is correct
13 Runtime error 488 ms 518204 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -