170872025-05-21 15:54:19tomi7Négyzetrács festéscpp17Wrong answer 0/100405ms11564 KiB
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, m;cin>>n>>m;
    vector<int> feketejobb;
    vector<int> feherjobb;
    vector<int> feketebal;
    vector<int> feherbal;
    vector<int> pref;
    vector<int> pref1;
    vector<int> pref2;
    vector<int> pref3;
    for(int i=0;i<n+m-1;i++){
        int x;cin>>x;
        if(i%2==0){
            if(pref.size()!=0){
                pref.push_back(pref.back()+x);
            }else{
                pref.push_back(x);
            }
            feketejobb.push_back(x);
        }else{
            if(pref1.size()!=0){
                pref1.push_back(pref1.back()+x);
            }else{
                pref1.push_back(x);
            }
            feherjobb.push_back(x);
        }
    }
    for(int i=0;i<n+m-1;i++){
        int x;cin>>x;
        if(m%2==1 && i%2==0 || m%2==0 && i%2==1){
            if(pref2.size()!=0){
                pref2.push_back(pref2.back()+x);
            }else{
                pref2.push_back(x);
            }
            feketebal.push_back(x);
        }else{
            if(pref3.size()!=0){
                pref3.push_back(pref3.back()+x);
            }else{
                pref3.push_back(x);
            }
            feherbal.push_back(x);
        }
    }
/*    for(int y: feketebal){
        cout<<y<<' ';
    }
    cout<<endl;
    for(int y: feherbal){
        cout<<y<<' ';
    }
    cout<<endl;
    for(int y: feketejobb){
        cout<<y<<' ';
    }
    cout<<endl;
    for(int y: feherjobb){
        cout<<y<<' ';
    }*/
  //  cout<<endl;
    vector<int> dpjobb;
    vector<int> dpbal;
    vector<int> dpdpjobb;
    vector<int> dddpbal;
    dpjobb.push_back(feketejobb[0]);
    dpbal.push_back(feketebal[0]);
    dpdpjobb.push_back(feherjobb[0]);
    dddpbal.push_back(feherbal[0]);
    while(dpjobb.size()!=(n+m)/2){
        if(dpjobb.size()<=m/2){
            dpjobb.push_back(dpjobb.back()+feketejobb[dpjobb.size()]);
            dpbal.push_back(dpbal.back()+feketebal[dpbal.size()]);
        }else{
            dpjobb.push_back(min(dpjobb.back()+feketejobb[dpjobb.size()], dpbal[dpjobb.size()-m/2]+pref[dpjobb.size()]-pref[dpjobb.size()-m/2]));
            dpbal.push_back(min(dpbal.back()+feketebal[dpbal.size()], dpjobb[dpbal.size()-m/2]+pref2[dpbal.size()]-pref2[dpbal.size()-m/2]));
        }
   //     cout<<dpjobb.back()<<' '<<dpbal.back()<<'\n';
    }
    while(dddpbal.size()!=(n+m)/2){
        if(dpdpjobb.size()<=m/2){
            dpdpjobb.push_back(dpdpjobb.back()+feherjobb[dpdpjobb.size()]);
            dddpbal.push_back(dddpbal.back()+feherbal[dddpbal.size()]);
        }else{
            dpdpjobb.push_back(min(dpdpjobb.back()+feherjobb[dpdpjobb.size()], dddpbal[dpdpjobb.size()-m/2]+pref1[dpdpjobb.size()]-pref1[dpdpjobb.size()-m/2]));
            dddpbal.push_back(min(dddpbal.back()+feherbal[dddpbal.size()], dpdpjobb[dddpbal.size()-m/2]+pref3[dddpbal.size()]-pref3[dddpbal.size()-m/2]));
        }
 //       cout<<dpdpjobb.back()<<' '<<dddpbal.back()<<'\n';
    }
    cout<<min(dpjobb.back(), dpbal.back())+min(dpdpjobb.back(), dddpbal.back());
}
SubtaskSumTestVerdictTimeMemory
subtask10/10
1Accepted1ms508 KiB
2Accepted1ms512 KiB
3Wrong answer1ms316 KiB
4Wrong answer1ms320 KiB
5Accepted1ms316 KiB
6Wrong answer1ms316 KiB
7Wrong answer1ms508 KiB
8Wrong answer1ms316 KiB
9Wrong answer1ms316 KiB
subtask20/10
1Wrong answer1ms316 KiB
2Wrong answer1ms316 KiB
3Wrong answer1ms508 KiB
4Wrong answer1ms500 KiB
5Wrong answer1ms316 KiB
6Wrong answer1ms316 KiB
7Wrong answer1ms316 KiB
8Wrong answer1ms316 KiB
9Wrong answer1ms316 KiB
subtask30/10
1Wrong answer1ms384 KiB
2Wrong answer1ms316 KiB
3Wrong answer1ms316 KiB
4Wrong answer1ms316 KiB
5Wrong answer1ms316 KiB
6Wrong answer1ms316 KiB
7Wrong answer1ms316 KiB
8Wrong answer1ms320 KiB
9Wrong answer1ms316 KiB
10Wrong answer1ms316 KiB
subtask40/20
1Wrong answer4ms316 KiB
2Wrong answer4ms316 KiB
3Wrong answer4ms316 KiB
4Wrong answer4ms316 KiB
5Wrong answer4ms432 KiB
6Wrong answer2ms396 KiB
7Wrong answer2ms316 KiB
8Wrong answer3ms416 KiB
9Wrong answer2ms400 KiB
10Wrong answer3ms316 KiB
11Wrong answer3ms316 KiB
12Wrong answer3ms484 KiB
13Wrong answer3ms456 KiB
subtask50/10
1Wrong answer190ms5848 KiB
2Wrong answer188ms5984 KiB
3Wrong answer188ms5848 KiB
4Wrong answer195ms5876 KiB
5Wrong answer202ms5916 KiB
6Wrong answer172ms6000 KiB
7Runtime error1ms316 KiB
subtask60/20
1Wrong answer405ms11524 KiB
2Wrong answer379ms11564 KiB
3Wrong answer382ms11524 KiB
4Wrong answer386ms11528 KiB
5Wrong answer384ms11548 KiB
6Wrong answer284ms11472 KiB
7Wrong answer368ms11544 KiB
subtask70/20
1Wrong answer173ms5916 KiB
2Wrong answer179ms5932 KiB
3Wrong answer188ms5868 KiB
4Wrong answer143ms5916 KiB
5Wrong answer190ms5804 KiB
6Wrong answer187ms5916 KiB
7Wrong answer145ms5892 KiB
8Wrong answer188ms5896 KiB
9Wrong answer190ms5940 KiB
10Wrong answer197ms6096 KiB
11Wrong answer216ms6560 KiB
12Wrong answer239ms7160 KiB
13Wrong answer287ms11468 KiB
14Wrong answer342ms11448 KiB