Submission #729208

#TimeUsernameProblemLanguageResultExecution timeMemory
729208YassineBenYounesCatfish Farm (IOI22_fish)C++17
Compilation error
0 ms0 KiB
#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; } void run_case(){ cout << max_weights(5, 4, {0, 1, 4, 3}, {0, 0, 0, 0}, {5, 2, 1, 3}) << endl; } int main(){ init(); speed; int t; //cin >> t; t = 1; while(t--){ run_case(); } } /* NEVER GIVE UP! DOING SMTHNG IS BETTER THAN DOING NTHNG!!! Your Guide when stuck: - Continue keyword only after reading the whole input - Don't use memset with testcases - Check for corner cases(n=1, n=0) - Check where you declare n(Be careful of declaring it globally and in main) */

Compilation message (stderr)

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);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccOX2Bud.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccEy964g.o:fish.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status