oj.uz

답안 #1026461

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1026461 2024-07-18T06:24:17 Z Mardonbekhazratov 메기 농장 (IOI22_fish) C++17
9 / 100
 70 ms 10868 KB 
#include "fish.h"

#include <iostream>
#include <vector>
#include <tuple>
#include <set>
#include <algorithm>
#include <map>

using namespace std;

#define ff first
#define ss second
#define ll long long

template<typename T,typename S>
T max(T a,S b){return a>b?a:b;}

int n,m;
vector<int>x,y,w;
ll ans=0;

ll sub2(){
    ll cur=0;
        if(n==2){
            for(int i=0;i<m;i++){
                if(x[i]) cur+=w[i];
                else ans+=w[i];
            }
            return max(ans,cur);
        }
        vector<pair<int,int>>a,b;
        for(int i=0;i<m;i++){
            if(x[i]&1) cur+=w[i],a.push_back({y[i],w[i]});
            else b.push_back({y[i],w[i]});
        }
        sort(a.begin(),a.end());
        sort(b.begin(),b.end());
        ans=cur;
        int j=0;
        for(auto [g,f]:b){
            cur+=f;
            while(j<a.size() && a[j].ff<=g) cur-=a[j].ss,j++;
            ans=max(ans,cur);
        }
        return ans;
}

ll sub3(){
    vector<pair<int,int>>a;
    for(int i=0;i<m;i++) a.push_back({x[i],w[i]});
    a.push_back({n,0});
    sort(a.begin(),a.end());
    int last=-1;
    vector<int>b={0};
    for(int i=0;i<=m;i++){
        if(a[i].ff-last==1) b.push_back(a[i].ss);
        else{
            ll cur=0;
            vector<ll>pref(b.size()+1),suff(b.size()+2);
            pref[0]=0;
            suff[b.size()+1]=0;
            for(int i=1;i<=b.size();i++){
                pref[i]=pref[i-1];
                if(i>2){
                    pref[i]=max(pref[i],pref[i-3]+b[i-1]+b[i-3]);
                }
                else{
                    pref[i]=max(pref[i],b[i-1]);
                }
            }
            for(int i=b.size();i>0;i--){
                suff[i]=suff[i+1];
                if(b.size()-i>1){
                    suff[i]=max(suff[i],suff[i+3]+b[i-1]+b[i+1]);
                }
                else{
                    suff[i]=max(suff[i],b[i-1]);
                }
            }
            for(int i=0;i<=b.size();i++) cur=max(cur,pref[i]+suff[i+1]);
            ans+=cur;
            vector<int>ne;
            swap(ne,b);
            b.push_back(a[i].ss);
        }
        last=a[i].ff;
    }
    
            ll cur=0;
            vector<ll>pref(b.size()+1),suff(b.size()+2);
            pref[0]=0;
            suff[b.size()+1]=0;
            for(int i=1;i<=b.size();i++){
                pref[i]=pref[i-1];
                if(i>2){
                    pref[i]=max(pref[i],pref[i-3]+b[i-1]+b[i-3]);
                }
                else{
                    pref[i]=max(pref[i],b[i-1]);
                }
            }
            for(int i=b.size();i>0;i--){
                suff[i]=suff[i+1];
                if(b.size()-i>1){
                    suff[i]=max(suff[i],suff[i+3]+b[i-1]+b[i+1]);
                }
                else{
                    suff[i]=max(suff[i],b[i-1]);
                }
            }
            for(int i=0;i<=b.size();i++) cur=max(cur,pref[i]+suff[i+1]);
            ans+=cur;
    return ans;
}

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
    tie(n,m,x,y,w)=tie(N,M,X,Y,W);
    bool su1=true,su2=true,su3=true;
    for(int i=0;i<m;i++){
        if(x[i]%2==1) su1=false;
        if(x[i]>1) su2=false;
        if(y[i]!=0) su3=false;
    }
    if(su1){for(int i=0;i<m;i++) ans+=w[i];return ans;}
    if(su2) return sub2();
    if(su3) return sub3();
    return ans;
}

Compilation message

fish.cpp: In function 'long long int sub2()':
fish.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             while(j<a.size() && a[j].ff<=g) cur-=a[j].ss,j++;
      |                   ~^~~~~~~~~
fish.cpp: In function 'long long int sub3()':
fish.cpp:63:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |             for(int i=1;i<=b.size();i++){
      |                         ~^~~~~~~~~~
fish.cpp:81:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |             for(int i=0;i<=b.size();i++) cur=max(cur,pref[i]+suff[i+1]);
      |                         ~^~~~~~~~~~
fish.cpp:94:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |             for(int i=1;i<=b.size();i++){
      |                         ~^~~~~~~~~~
fish.cpp:112:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |             for(int i=0;i<=b.size();i++) cur=max(cur,pref[i]+suff[i+1]);
      |                         ~^~~~~~~~~~

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 3160 KB Output is correct
2 Correct 22 ms 3920 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 60 ms 10836 KB Output is correct
6 Correct 70 ms 10868 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 51 ms 7628 KB Output is correct
3 Correct 49 ms 9160 KB Output is correct
4 Correct 14 ms 3160 KB Output is correct
5 Correct 17 ms 3932 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 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 20 ms 4308 KB Output is correct
13 Correct 24 ms 5068 KB Output is correct
14 Correct 20 ms 4208 KB Output is correct
15 Correct 31 ms 4448 KB Output is correct
16 Correct 20 ms 4084 KB Output is correct
17 Correct 22 ms 4440 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 14 ms 3000 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '20781023892842'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '3', found: '0'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '3', found: '0'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '3', found: '0'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 14 ms 3000 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '20781023892842'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 3160 KB Output is correct
2 Correct 22 ms 3920 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 60 ms 10836 KB Output is correct
6 Correct 70 ms 10868 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 51 ms 7628 KB Output is correct
9 Correct 49 ms 9160 KB Output is correct
10 Correct 14 ms 3160 KB Output is correct
11 Correct 17 ms 3932 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 20 ms 4308 KB Output is correct
19 Correct 24 ms 5068 KB Output is correct
20 Correct 20 ms 4208 KB Output is correct
21 Correct 31 ms 4448 KB Output is correct
22 Correct 20 ms 4084 KB Output is correct
23 Correct 22 ms 4440 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Incorrect 14 ms 3000 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '20781023892842'
27 Halted 0 ms 0 KB -