oj.uz

답안 #1039230

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1039230 2024-07-30T14:57:22 Z Maite_Morale 메기 농장 (IOI22_fish) C++17
9 / 100
 150 ms 63088 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vll vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define S second
#define F first
long long max_weights(int n,int m,vector<int> X,vector<int> Y,vector<int> W) {
    vector<vll> v (n+5,vll {-1}), w(n+5,vll {0});
    vector<vpll> la (n+5,vpll {{-1,0}});
    ll r=0;
    for(int i=0;i<m;i++){
        if(X[i]>0)la[X[i]].push_back({Y[i],0});
        la[X[i]+1].push_back({Y[i],-W[i]});
        la[X[i]+1].push_back({Y[i]-1,0});
        la[X[i]+2].push_back({Y[i],0});
    }
    for(int i=0;i<=n;i++){
        sort(la[i].begin(),la[i].end());
        for(int j=1;j<la[i].size();j++){
            if(la[i][j].F==la[i][j-1].F)continue;
            v[i].push_back(la[i][j].F);
            w[i].push_back(-la[i][j].S);
            w[i][j]+=w[i][j-1];
        }
    }
    vll t1{{}},t2{{}},t3{{}},t4{{}};
    vll h2[2]={{},{}},h1[2]={{0},{0}};
    for(int i=1;i<=n;i++){
        t1=h1[0];
        for(int j=0;j<h1[0].size();j++){      
            t1[j]=t1[j]-w[i-1][j];
            if(j>0)t1[j]=max(t1[j],t1[j-1]);   //dp[i-1][k<j][0]-co[i][k<j]
        }
        t2=h2[1];
        for(int j=0;j<h2[0].size();j++){
            if(j>0)t2[j]=max(t2[j],t2[j-1]);//dp[i-2][k<j][1]
        }
        t3=h2[1];ll p=v[i-1].size()-1;
        for(int j=h2[0].size()-1;j>=0;j--){
            while(p>=0 && v[i-1][p]>v[i-2][j])p--;
            if(p>-1)t3[j]=t3[j]+w[i-1][j];                //dp[]
            if(j+1<h2[0].size())t3[j]=max(t3[j],t3[j+1]);
        }
        t4=h1[1];p=v[i].size()-1;
        for(int j=h1[1].size()-1;j>=0;j--){
            while(p>=0 && v[i][p]>v[i-1][j])p--;
            if(p>-1)t4[j]=t4[j]+w[i][p];
            if(j+1<h1[1].size())t4[j]=max(t4[j],t4[j+1]);
        }
        ll p1=-1,p2=-1;
        vll h[2]={{},{}};
        for(int j=0;j<v[i].size();j++){
            ll dp[2]={0,0};
            if(i>=2){
                while(p1+1<v[i-1].size() && v[i-1][p1+1]<=v[i][j])p1++;
                while(p2+1<v[i-2].size() && v[i-1][p2+1]<=v[i][j])p2++;
                if(p1>-1)             dp[0]=max(dp[0],t1[p1]+w[i-1][p1]);//dp[i-1][k][0]-co[i-1][k]+co[i-1][j]
                if(p2>-1)             dp[0]=max(dp[0],t2[p2]+w[i-1][p1]);//dp[i-2][k][1]           +co[i-1][j]   
                if(p2<v[i-2].size()-1)dp[0]=max(dp[0],t3[p2+1]);         //dp[i-2][k][1]+co[i-1][k] 
                dp[1]=dp[0];
                if(p1<v[i-1].size()-1)dp[1]=max(dp[1],t4[p2+1]-w[i][j]); //dp[i-1][k][1]+co [i] [k]-co[i][j]
            }
            h[0].push_back(dp[0]);
            h[1].push_back(dp[1]);
            r=max(h[0].back(),max(r,h[1].back()));
        }
        h2[0]=h1[0];h1[0]=h[0];
        h2[1]=h1[1];h1[1]=h[1];
    }
return r;
}/*
int 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;
}
//*/
/*
0 0 0 1 0
0 0 3 0 0
5 0 0 0 0 
0 2 0 0 0
0 0 0 0 0 
*/

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:21:22: 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]
   21 |         for(int j=1;j<la[i].size();j++){
      |                     ~^~~~~~~~~~~~~
fish.cpp:32:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for(int j=0;j<h1[0].size();j++){
      |                     ~^~~~~~~~~~~~~
fish.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for(int j=0;j<h2[0].size();j++){
      |                     ~^~~~~~~~~~~~~
fish.cpp:44:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |             if(j+1<h2[0].size())t3[j]=max(t3[j],t3[j+1]);
      |                ~~~^~~~~~~~~~~~~
fish.cpp:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             if(j+1<h1[1].size())t4[j]=max(t4[j],t4[j+1]);
      |                ~~~^~~~~~~~~~~~~
fish.cpp:54:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for(int j=0;j<v[i].size();j++){
      |                     ~^~~~~~~~~~~~
fish.cpp:57:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |                 while(p1+1<v[i-1].size() && v[i-1][p1+1]<=v[i][j])p1++;
      |                       ~~~~^~~~~~~~~~~~~~
fish.cpp:58:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |                 while(p2+1<v[i-2].size() && v[i-1][p2+1]<=v[i][j])p2++;
      |                       ~~~~^~~~~~~~~~~~~~
fish.cpp:61:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |                 if(p2<v[i-2].size()-1)dp[0]=max(dp[0],t3[p2+1]);         //dp[i-2][k][1]+co[i-1][k]
      |                    ~~^~~~~~~~~~~~~~~~
fish.cpp:63:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |                 if(p1<v[i-1].size()-1)dp[1]=max(dp[1],t4[p2+1]-w[i][j]); //dp[i-1][k][1]+co [i] [k]-co[i][j]
      |                    ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 49 ms 47556 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 91 ms 63088 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 16728 KB Output is correct
2 Correct 25 ms 16728 KB Output is correct
3 Correct 59 ms 23972 KB Output is correct
4 Correct 49 ms 22872 KB Output is correct
5 Correct 85 ms 33104 KB Output is correct
6 Correct 77 ms 32444 KB Output is correct
7 Correct 83 ms 33108 KB Output is correct
8 Correct 99 ms 33108 KB Output is correct

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Runtime error 1 ms 604 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Runtime error 1 ms 604 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Runtime error 1 ms 604 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 16728 KB Output is correct
2 Correct 25 ms 16728 KB Output is correct
3 Correct 59 ms 23972 KB Output is correct
4 Correct 49 ms 22872 KB Output is correct
5 Correct 85 ms 33104 KB Output is correct
6 Correct 77 ms 32444 KB Output is correct
7 Correct 83 ms 33108 KB Output is correct
8 Correct 99 ms 33108 KB Output is correct
9 Correct 150 ms 35012 KB Output is correct
10 Runtime error 64 ms 50256 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 49 ms 47556 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -