제출 #645929

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
645929		lukameladze	메기 농장 (IOI22_fish)	C++17	100 / 100	414 ms	138804 KiB

fish

# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair <int, int>
#define pb push_back
const int N = 3e5 + 5;
const long long inf = 1e17;
int n,m,x[N],y[N],w[N];
vector <pii> v[N];
long long ans;
vector <long long> pot[N],pr[N],pr_dp[N],sf_dp[N], dp[N],dp_inc[N],dp_dec[N];
int go(int idx, long long val) {
    int le = 0;
    int ri = pot[idx].size() - 1;
    int ans = - 1;
    while (le <= ri) {
        int mid = (le + ri) / 2;
        if (pot[idx][mid] <= val) {
            ans = mid;
            le = mid + 1;
        } else ri = mid - 1;
    }    
    return ans;
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
    m = M; 
    n = N;
    for (int i = 0; i < m; i++) {
        x[i] = X[i] + 1;
        y[i] = Y[i] + 1;
        w[i] = W[i];
        v[x[i]].pb({y[i] - 1, w[i]});
        pot[x[i]].pb(y[i] - 1);
    }
    for (int i = 1; i <= n; i++) {
        v[i].pb({0,0}); v[i].pb({n,0}); sort(v[i].begin(),v[i].end());
        pot[i].pb(0); pot[i].pb(n);   sort(pot[i].begin(),pot[i].end());
        pr[i] = vector <long long> (v[i].size() + 5, 0);
        for (int j = 0; j < v[i].size(); j++) {
            pr[i][j] = pr[i][j - (j != 0)] + v[i][j].s;
        }
    }
    /*
    for (int i = 1; i <= n; i++) {
        cout<<i<<" ----- > ";
        for (int po : pot[i]) cout<<po<<" ";
        cout<<"\n";
    }*/
    for (int i = 1; i <= n; i++) {
        dp[i] = vector <long long> (pot[i].size() + 5, 0);
        dp_inc[i] = dp_dec[i] = vector < long long > (pot[i].size() + 5, 0);
        sf_dp[i] = pr_dp[i] = vector <long long> (pot[i].size() +  5, -inf);

        if (i > 1) {
            // if ( a >= b)
            long long mx = 0;
            for (int j = 0; j < v[i - 1].size(); j++) mx = max(mx, dp_inc[i - 1][j]), mx = max(mx, dp_dec[i - 1][j]);
            dp_inc[i][0] = max(dp_inc[i][0], mx);
            dp_dec[i][0] = max(dp_dec[i][0], mx);
            for (int j = 0; j < pot[i].size(); j++) {
                int a = pot[i][j];
                int prid = go(i - 1, a - 1);
                // dp[i][j] = dp[i - 1][k] + (pr[i - 1][j] - pr[i - 1][k])
                // dp[i][j] = (dp[i - 1][k] - pr[i - 1][k])  + pr[i - 1][j]
                
                if (prid == -1) {
                    dp_inc[i][j] = mx;
                    continue;
                }
                dp_inc[i][j] = max(dp_inc[i][j], pr_dp[i - 1][prid] + pr[i - 1][prid]);
            }
            dp_inc[i][pot[i].size() - 1] = max(dp_inc[i][pot[i].size() - 1], max(dp_inc[i - 1][pot[i - 1].size() - 1], dp_dec[i - 1][pot[i - 1].size() - 1]));
            dp_dec[i][pot[i].size() - 1] = dp_inc[i][pot[i].size() - 1];
            // if ( a < b ) 
            for (int j = 0; j < pot[i].size(); j++) {
                int a = pot[i][j];
                int prid = go(i - 1, a - 1); prid++;
                dp_dec[i][j] = max(dp_dec[i][j], sf_dp[i - 1][prid] - (j ? pr[i][j - 1] : 0)); // ?
            }
            
        }
        /*for (int j = 0; j < pot[i].size(); j++) {
            if (dp_dec[i][j])cout<<i<<" "<<pot[i][j]<<" "<<dp_dec[i][j]<<"\n";
        }*/
        
        
        if (i == n) continue;
        
        
        pr_dp[i][0] = dp_inc[i][0];
        for (int j = 1; j < pot[i].size(); j++) {
            pr_dp[i][j] = max(pr_dp[i][j - 1], dp_inc[i][j] - pr[i][j - 1]); // j - 1
        }
        set <pii> s;
        long long sf_sum = 0;
        for (pii x : v[i + 1]) {
            s.insert({x.f, x.s});
            sf_sum += x.s; 
        }
        int sz = pot[i].size();
        for (int j = sz - 1; j >= 0; j--) {
            while (s.size() && (*--s.end()).f >= pot[i][j]) {
                sf_sum -= (*--s.end()).s;
                s.erase(--s.end());
            }
            sf_dp[i][j] = max(sf_dp[i][j + 1], dp_dec[i][j] + sf_sum);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < pot[i].size(); j++) {
            ans = max(ans, dp_inc[i][j]);
            ans = max(ans, dp_dec[i][j]);
        }
    }
    return ans;
}
/*
signed main() {
  int N, M;
  assert(2 == scanf("%d %d", &N, &M));

  std::vector<int> X(M), Y(M), W(M);
  for (int i = 0; i < M; ++i) {
    assert(3 == scanf("%d %d %d", &X[i], &Y[i], &W[i]));
  }

  long long result = max_weights(N, M, X, Y, W);
  printf("%lld\n", result);
  return 0;
}*/

컴파일 시 표준 에러 (stderr) 메시지

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:40:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for (int j = 0; j < v[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~
fish.cpp:58:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             for (int j = 0; j < v[i - 1].size(); j++) mx = max(mx, dp_inc[i - 1][j]), mx = max(mx, dp_dec[i - 1][j]);
      |                             ~~^~~~~~~~~~~~~~~~~
fish.cpp:61:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |             for (int j = 0; j < pot[i].size(); j++) {
      |                             ~~^~~~~~~~~~~~~~~
fish.cpp:76:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |             for (int j = 0; j < pot[i].size(); j++) {
      |                             ~~^~~~~~~~~~~~~~~
fish.cpp:92:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         for (int j = 1; j < pot[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~
fish.cpp:111:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         for (int j = 0; j < pot[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 9 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 17 / 17
• Subtask 7: 14 / 14
• Subtask 8: 16 / 16