#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pbds tree<pair<ll, ll>, null_type, less<pair<ll,ll>>,rb_tree_tag, tree_order_statistics_node_update>
using namespace __gnu_pbds;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} // greatest common divisor (PGCD)
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);} // least common multiple (PPCM)
int dx[8] = {1, 0, 0, -1, 1, 1, -1, -1};
int dy[8] = {0, 1, -1, 0, 1, -1, -1, 1};
#define endl "\n"
#define ss second
#define ff first
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int,int>>
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define vdd vector<pdd>
#define speed ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
////////////////////Only Clear Code//////////////////////////
void usaco_problem(){
freopen("milkvisits.in", "r", stdin);
freopen("milkvisits.out", "w", stdout);
}
void init(){
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE
}
const int mx = 302;
const int mx1 = 1e5+1;
const int LOG = 25;
const int inf = 1e9;
const ll mod = 1e8;
ll dp[302][302][3][3];
ll dp1[mx1][20][3][3];
ll sum1[mx][mx];
vll sum[mx1];
set<int> pos3[mx1];
vi pos2[mx1];
set<int> pos1[mx];
vi pos[mx];
vi arr[mx1];
ll ooo[mx1];
int n;
ll calc(int cur, int m){
return sum1[cur][m];
}
ll solve(int cur,int l, int type, int dis){
if(cur == n+1)return 0;
ll ans = 0;
if(dp[cur][l+1][type+1][dis-1] != -1)return dp[cur][l+1][type+1][dis-1];
int last1 = 0, last2 = 0;
if(type == -1){
if(dis == 2 && cur >= 3 && l != -1)last2 = pos[cur-2][l];
}
else{
if(cur >= 2 && l != -1)last1 = pos[cur-1][l];
}
for(int ind = 0; ind < pos[cur].size();ind++){
int i = pos[cur][ind];
if(type == 1 && i > last1)continue;
ll s = 0;
if(cur-1 >= 1)s += calc(cur-1,i) - calc(cur-1,min(i, last1));
if(cur+1 <= n)s += calc(cur+1,i);
s -= calc(cur,min(i, last1));
if(type == -1 && i > last1){
s -= calc(cur-1,min(i, last2));
}
int x = (last1 > i);
ans = max(ans, solve(cur+1, ind, x, 1) + s);
}
ans = max(ans, solve(cur+1, l, -1, min(dis+1, 3)));
return dp[cur][l+1][type+1][dis-1] = ans;
}
ll calc1(int cur, int m){
ll s = 0;
if(sum[cur].empty())return 0;
pll p = {m, 0};
int x = lower_bound(all(sum[cur]), p) - sum[cur].begin();
if(x == sum[cur].size()){
return sum[cur].back().ss;
}
if(m != sum[cur][x].ff){
x--;
if(x >= 0){
s = sum[cur][x].ss;
}
}
else{
s = sum[cur][x].ss;
}
return s;
}
ll solve1(int cur,int l, int type, int dis){
if(cur == n+1)return 0;
ll ans = 0;
if(dp1[cur][l+1][type+1][dis-1] != -1)return dp1[cur][l+1][type+1][dis-1];
int last1 = 0, last2 = 0;
if(type == -1){
if(dis == 2 && cur >= 3 && l != -1)last2 = pos2[cur-2][l];
}
else{
if(cur >= 2 && l != -1)last1 = pos2[cur-1][l];
}
for(int ind = 0; ind < pos2[cur].size();ind++){
int i = pos2[cur][ind];
if(type == 1 && i > last1)continue;
ll s = 0;
if(cur-1 >= 1)s += calc1(cur-1,i) - calc1(cur-1,min(i, last1));
if(cur+1 <= n)s += calc1(cur+1,i);
s -= calc1(cur,min(i, last1));
if(type == -1 && i > last1){
s -= calc1(cur-1,min(i, last2));
}
int x = (last1 > i);
ans = max(ans, solve1(cur+1, ind, x, 1) + s);
}
ans = max(ans, solve1(cur+1, l, -1, min(dis+1, 3)));
return dp1[cur][l+1][type+1][dis-1] = ans;
}
ll max_weights(int N, int m, vi x,vi y,vi w){
n = N;
bool one = 1;
bool two = 1;
for(int g : x){
if(g % 2 == 1)one = 0;
if(g >= 2)two = 0;
}
if(one){
ll ans = 0;
for(int x : w){
ans += x;
}
return ans;
}
if(two){
ll ans1 = 0, ans2 = 0;
for(int i = 0; i < x.size();i++){
if(x[i] == 0)ans1 += w[i];
else if(x[i] == 1)ans2 += w[i];
}
if(n == 2){
return max(ans1, ans2);
}
vi v(N);
for(int i = 0; i < m;i++){
if(x[i] == 0){
v[y[i]] = w[i];
}
}
vi v1(N);
for(int i = 0; i < m;i++){
if(x[i] == 1){
v1[y[i]] = w[i];
}
}
ll kk = 0;
for(int i = 0; i < n;i++){
kk += v[i];
ooo[i] = kk;
}
ll l = 0;
ll cnt = 0;
for(int i = n-1;i > 0;i--){
l += v1[i];
ll a = l + ooo[i-1];
cnt = max(cnt, a);
}
return max(ans1, max(cnt, ans2));
}
if(n <= 300){
for(int i = 0; i < m;i++){
x[i]++;
y[i]++;
ll a = w[i];
sum1[x[i]][y[i]] += a;
if(x[i]-1 >= 1)pos1[x[i]-1].insert(y[i]);
if(x[i]+1 <= n)pos1[x[i]+1].insert(y[i]);
}
for(int i = 1; i <= n;i++){
for(int x : pos1[i]){
pos[i].pb(x);
}
}
for(int i = 1; i <= n;i++){
for(int j = 2;j <= n;j++){
sum1[i][j] += sum1[i][j-1];
}
}
memset(dp, -1, sizeof dp);
ll ans = solve(1, -1, -1, 3);
return ans;
}
for(int i = 0; i < m;i++){
x[i]++;
y[i]++;
ll a = w[i];
sum[x[i]].pb({y[i], w[i]});
if(x[i]-1 >= 1)pos3[x[i]-1].insert({y[i], 1});
if(x[i]+1 <= n)pos3[x[i]+1].insert({y[i], -1});
}
for(int i = 1; i <= n;i++){
sort(all(sum[i]));
for(int x : pos3[i]){
pos2[i].pb(x);
}
for(int j = 1;j < sum[i].size();j++){
sum[i][j].ss += sum[i][j-1].ss;
}
}
memset(dp1, -1, sizeof dp1);
ll ans = solve1(1, -1, -1, 3);
return ans;
}
Compilation message
fish.cpp: In function 'll solve(int, int, int, int)':
fish.cpp:87:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for(int ind = 0; ind < pos[cur].size();ind++){
| ~~~~^~~~~~~~~~~~~~~~~
fish.cpp: In function 'll calc1(int, int)':
fish.cpp:109:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | if(x == sum[cur].size()){
| ~~^~~~~~~~~~~~~~~~~~
fish.cpp: In function 'll solve1(int, int, int, int)':
fish.cpp:134:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | for(int ind = 0; ind < pos2[cur].size();ind++){
| ~~~~^~~~~~~~~~~~~~~~~~
fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:168:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
168 | for(int i = 0; i < x.size();i++){
| ~~^~~~~~~~~~
fish.cpp:227:12: warning: unused variable 'a' [-Wunused-variable]
227 | ll a = w[i];
| ^
fish.cpp:237:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
237 | for(int j = 1;j < sum[i].size();j++){
| ~~^~~~~~~~~~~~~~~
fish.cpp: In function 'void usaco_problem()':
fish.cpp:33:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
33 | freopen("milkvisits.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:34:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
34 | freopen("milkvisits.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp: In function 'void init()':
fish.cpp:40:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | freopen("input.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:42:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
42 | freopen("output.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
38 ms |
15316 KB |
Output is correct |
2 |
Correct |
37 ms |
16076 KB |
Output is correct |
3 |
Correct |
8 ms |
11988 KB |
Output is correct |
4 |
Correct |
7 ms |
12080 KB |
Output is correct |
5 |
Correct |
104 ms |
25436 KB |
Output is correct |
6 |
Correct |
111 ms |
25688 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
12080 KB |
Output is correct |
2 |
Correct |
63 ms |
20108 KB |
Output is correct |
3 |
Correct |
75 ms |
21812 KB |
Output is correct |
4 |
Correct |
34 ms |
15288 KB |
Output is correct |
5 |
Correct |
38 ms |
16060 KB |
Output is correct |
6 |
Correct |
8 ms |
11988 KB |
Output is correct |
7 |
Correct |
7 ms |
12088 KB |
Output is correct |
8 |
Correct |
7 ms |
11988 KB |
Output is correct |
9 |
Correct |
7 ms |
11988 KB |
Output is correct |
10 |
Correct |
7 ms |
12028 KB |
Output is correct |
11 |
Correct |
8 ms |
11988 KB |
Output is correct |
12 |
Correct |
34 ms |
16740 KB |
Output is correct |
13 |
Correct |
38 ms |
17724 KB |
Output is correct |
14 |
Correct |
34 ms |
16740 KB |
Output is correct |
15 |
Correct |
50 ms |
17224 KB |
Output is correct |
16 |
Correct |
36 ms |
16740 KB |
Output is correct |
17 |
Correct |
37 ms |
17228 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
11988 KB |
Output is correct |
2 |
Correct |
76 ms |
166964 KB |
Output is correct |
3 |
Correct |
205 ms |
176536 KB |
Output is correct |
4 |
Correct |
147 ms |
174552 KB |
Output is correct |
5 |
Correct |
272 ms |
186700 KB |
Output is correct |
6 |
Correct |
252 ms |
185932 KB |
Output is correct |
7 |
Correct |
291 ms |
186620 KB |
Output is correct |
8 |
Correct |
270 ms |
186672 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
18516 KB |
Output is correct |
2 |
Correct |
10 ms |
18516 KB |
Output is correct |
3 |
Correct |
8 ms |
12080 KB |
Output is correct |
4 |
Correct |
8 ms |
12080 KB |
Output is correct |
5 |
Correct |
7 ms |
12088 KB |
Output is correct |
6 |
Correct |
8 ms |
12080 KB |
Output is correct |
7 |
Correct |
7 ms |
11988 KB |
Output is correct |
8 |
Correct |
10 ms |
18476 KB |
Output is correct |
9 |
Correct |
14 ms |
18872 KB |
Output is correct |
10 |
Correct |
17 ms |
19380 KB |
Output is correct |
11 |
Correct |
11 ms |
18900 KB |
Output is correct |
12 |
Correct |
11 ms |
19388 KB |
Output is correct |
13 |
Correct |
10 ms |
18676 KB |
Output is correct |
14 |
Correct |
12 ms |
19284 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
18516 KB |
Output is correct |
2 |
Correct |
10 ms |
18516 KB |
Output is correct |
3 |
Correct |
8 ms |
12080 KB |
Output is correct |
4 |
Correct |
8 ms |
12080 KB |
Output is correct |
5 |
Correct |
7 ms |
12088 KB |
Output is correct |
6 |
Correct |
8 ms |
12080 KB |
Output is correct |
7 |
Correct |
7 ms |
11988 KB |
Output is correct |
8 |
Correct |
10 ms |
18476 KB |
Output is correct |
9 |
Correct |
14 ms |
18872 KB |
Output is correct |
10 |
Correct |
17 ms |
19380 KB |
Output is correct |
11 |
Correct |
11 ms |
18900 KB |
Output is correct |
12 |
Correct |
11 ms |
19388 KB |
Output is correct |
13 |
Correct |
10 ms |
18676 KB |
Output is correct |
14 |
Correct |
12 ms |
19284 KB |
Output is correct |
15 |
Correct |
10 ms |
19284 KB |
Output is correct |
16 |
Correct |
18 ms |
18876 KB |
Output is correct |
17 |
Correct |
662 ms |
24124 KB |
Output is correct |
18 |
Correct |
531 ms |
23784 KB |
Output is correct |
19 |
Correct |
437 ms |
23952 KB |
Output is correct |
20 |
Correct |
344 ms |
23536 KB |
Output is correct |
21 |
Correct |
275 ms |
23464 KB |
Output is correct |
22 |
Correct |
982 ms |
27708 KB |
Output is correct |
23 |
Correct |
59 ms |
20428 KB |
Output is correct |
24 |
Correct |
362 ms |
23100 KB |
Output is correct |
25 |
Correct |
13 ms |
19404 KB |
Output is correct |
26 |
Correct |
46 ms |
20372 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
18516 KB |
Output is correct |
2 |
Correct |
10 ms |
18516 KB |
Output is correct |
3 |
Correct |
8 ms |
12080 KB |
Output is correct |
4 |
Correct |
8 ms |
12080 KB |
Output is correct |
5 |
Correct |
7 ms |
12088 KB |
Output is correct |
6 |
Correct |
8 ms |
12080 KB |
Output is correct |
7 |
Correct |
7 ms |
11988 KB |
Output is correct |
8 |
Correct |
10 ms |
18476 KB |
Output is correct |
9 |
Correct |
14 ms |
18872 KB |
Output is correct |
10 |
Correct |
17 ms |
19380 KB |
Output is correct |
11 |
Correct |
11 ms |
18900 KB |
Output is correct |
12 |
Correct |
11 ms |
19388 KB |
Output is correct |
13 |
Correct |
10 ms |
18676 KB |
Output is correct |
14 |
Correct |
12 ms |
19284 KB |
Output is correct |
15 |
Correct |
10 ms |
19284 KB |
Output is correct |
16 |
Correct |
18 ms |
18876 KB |
Output is correct |
17 |
Correct |
662 ms |
24124 KB |
Output is correct |
18 |
Correct |
531 ms |
23784 KB |
Output is correct |
19 |
Correct |
437 ms |
23952 KB |
Output is correct |
20 |
Correct |
344 ms |
23536 KB |
Output is correct |
21 |
Correct |
275 ms |
23464 KB |
Output is correct |
22 |
Correct |
982 ms |
27708 KB |
Output is correct |
23 |
Correct |
59 ms |
20428 KB |
Output is correct |
24 |
Correct |
362 ms |
23100 KB |
Output is correct |
25 |
Correct |
13 ms |
19404 KB |
Output is correct |
26 |
Correct |
46 ms |
20372 KB |
Output is correct |
27 |
Correct |
78 ms |
154124 KB |
Output is correct |
28 |
Execution timed out |
1075 ms |
180772 KB |
Time limit exceeded |
29 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
11988 KB |
Output is correct |
2 |
Correct |
76 ms |
166964 KB |
Output is correct |
3 |
Correct |
205 ms |
176536 KB |
Output is correct |
4 |
Correct |
147 ms |
174552 KB |
Output is correct |
5 |
Correct |
272 ms |
186700 KB |
Output is correct |
6 |
Correct |
252 ms |
185932 KB |
Output is correct |
7 |
Correct |
291 ms |
186620 KB |
Output is correct |
8 |
Correct |
270 ms |
186672 KB |
Output is correct |
9 |
Correct |
446 ms |
195820 KB |
Output is correct |
10 |
Correct |
280 ms |
174976 KB |
Output is correct |
11 |
Correct |
480 ms |
197112 KB |
Output is correct |
12 |
Correct |
7 ms |
11988 KB |
Output is correct |
13 |
Correct |
7 ms |
12080 KB |
Output is correct |
14 |
Correct |
8 ms |
11988 KB |
Output is correct |
15 |
Correct |
7 ms |
12084 KB |
Output is correct |
16 |
Correct |
7 ms |
12080 KB |
Output is correct |
17 |
Correct |
10 ms |
18404 KB |
Output is correct |
18 |
Correct |
8 ms |
11964 KB |
Output is correct |
19 |
Correct |
7 ms |
11988 KB |
Output is correct |
20 |
Correct |
72 ms |
166968 KB |
Output is correct |
21 |
Correct |
70 ms |
167064 KB |
Output is correct |
22 |
Correct |
501 ms |
192968 KB |
Output is correct |
23 |
Correct |
937 ms |
210496 KB |
Output is correct |
24 |
Correct |
950 ms |
213816 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
38 ms |
15316 KB |
Output is correct |
2 |
Correct |
37 ms |
16076 KB |
Output is correct |
3 |
Correct |
8 ms |
11988 KB |
Output is correct |
4 |
Correct |
7 ms |
12080 KB |
Output is correct |
5 |
Correct |
104 ms |
25436 KB |
Output is correct |
6 |
Correct |
111 ms |
25688 KB |
Output is correct |
7 |
Correct |
8 ms |
12080 KB |
Output is correct |
8 |
Correct |
63 ms |
20108 KB |
Output is correct |
9 |
Correct |
75 ms |
21812 KB |
Output is correct |
10 |
Correct |
34 ms |
15288 KB |
Output is correct |
11 |
Correct |
38 ms |
16060 KB |
Output is correct |
12 |
Correct |
8 ms |
11988 KB |
Output is correct |
13 |
Correct |
7 ms |
12088 KB |
Output is correct |
14 |
Correct |
7 ms |
11988 KB |
Output is correct |
15 |
Correct |
7 ms |
11988 KB |
Output is correct |
16 |
Correct |
7 ms |
12028 KB |
Output is correct |
17 |
Correct |
8 ms |
11988 KB |
Output is correct |
18 |
Correct |
34 ms |
16740 KB |
Output is correct |
19 |
Correct |
38 ms |
17724 KB |
Output is correct |
20 |
Correct |
34 ms |
16740 KB |
Output is correct |
21 |
Correct |
50 ms |
17224 KB |
Output is correct |
22 |
Correct |
36 ms |
16740 KB |
Output is correct |
23 |
Correct |
37 ms |
17228 KB |
Output is correct |
24 |
Correct |
7 ms |
11988 KB |
Output is correct |
25 |
Correct |
76 ms |
166964 KB |
Output is correct |
26 |
Correct |
205 ms |
176536 KB |
Output is correct |
27 |
Correct |
147 ms |
174552 KB |
Output is correct |
28 |
Correct |
272 ms |
186700 KB |
Output is correct |
29 |
Correct |
252 ms |
185932 KB |
Output is correct |
30 |
Correct |
291 ms |
186620 KB |
Output is correct |
31 |
Correct |
270 ms |
186672 KB |
Output is correct |
32 |
Correct |
10 ms |
18516 KB |
Output is correct |
33 |
Correct |
10 ms |
18516 KB |
Output is correct |
34 |
Correct |
8 ms |
12080 KB |
Output is correct |
35 |
Correct |
8 ms |
12080 KB |
Output is correct |
36 |
Correct |
7 ms |
12088 KB |
Output is correct |
37 |
Correct |
8 ms |
12080 KB |
Output is correct |
38 |
Correct |
7 ms |
11988 KB |
Output is correct |
39 |
Correct |
10 ms |
18476 KB |
Output is correct |
40 |
Correct |
14 ms |
18872 KB |
Output is correct |
41 |
Correct |
17 ms |
19380 KB |
Output is correct |
42 |
Correct |
11 ms |
18900 KB |
Output is correct |
43 |
Correct |
11 ms |
19388 KB |
Output is correct |
44 |
Correct |
10 ms |
18676 KB |
Output is correct |
45 |
Correct |
12 ms |
19284 KB |
Output is correct |
46 |
Correct |
10 ms |
19284 KB |
Output is correct |
47 |
Correct |
18 ms |
18876 KB |
Output is correct |
48 |
Correct |
662 ms |
24124 KB |
Output is correct |
49 |
Correct |
531 ms |
23784 KB |
Output is correct |
50 |
Correct |
437 ms |
23952 KB |
Output is correct |
51 |
Correct |
344 ms |
23536 KB |
Output is correct |
52 |
Correct |
275 ms |
23464 KB |
Output is correct |
53 |
Correct |
982 ms |
27708 KB |
Output is correct |
54 |
Correct |
59 ms |
20428 KB |
Output is correct |
55 |
Correct |
362 ms |
23100 KB |
Output is correct |
56 |
Correct |
13 ms |
19404 KB |
Output is correct |
57 |
Correct |
46 ms |
20372 KB |
Output is correct |
58 |
Correct |
78 ms |
154124 KB |
Output is correct |
59 |
Execution timed out |
1075 ms |
180772 KB |
Time limit exceeded |
60 |
Halted |
0 ms |
0 KB |
- |