170872025-05-21 15:54:19tomi7Négyzetrács festéscpp17Hibás válasz 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());
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/10
1Elfogadva1ms508 KiB
2Elfogadva1ms512 KiB
3Hibás válasz1ms316 KiB
4Hibás válasz1ms320 KiB
5Elfogadva1ms316 KiB
6Hibás válasz1ms316 KiB
7Hibás válasz1ms508 KiB
8Hibás válasz1ms316 KiB
9Hibás válasz1ms316 KiB
subtask20/10
1Hibás válasz1ms316 KiB
2Hibás válasz1ms316 KiB
3Hibás válasz1ms508 KiB
4Hibás válasz1ms500 KiB
5Hibás válasz1ms316 KiB
6Hibás válasz1ms316 KiB
7Hibás válasz1ms316 KiB
8Hibás válasz1ms316 KiB
9Hibás válasz1ms316 KiB
subtask30/10
1Hibás válasz1ms384 KiB
2Hibás válasz1ms316 KiB
3Hibás válasz1ms316 KiB
4Hibás válasz1ms316 KiB
5Hibás válasz1ms316 KiB
6Hibás válasz1ms316 KiB
7Hibás válasz1ms316 KiB
8Hibás válasz1ms320 KiB
9Hibás válasz1ms316 KiB
10Hibás válasz1ms316 KiB
subtask40/20
1Hibás válasz4ms316 KiB
2Hibás válasz4ms316 KiB
3Hibás válasz4ms316 KiB
4Hibás válasz4ms316 KiB
5Hibás válasz4ms432 KiB
6Hibás válasz2ms396 KiB
7Hibás válasz2ms316 KiB
8Hibás válasz3ms416 KiB
9Hibás válasz2ms400 KiB
10Hibás válasz3ms316 KiB
11Hibás válasz3ms316 KiB
12Hibás válasz3ms484 KiB
13Hibás válasz3ms456 KiB
subtask50/10
1Hibás válasz190ms5848 KiB
2Hibás válasz188ms5984 KiB
3Hibás válasz188ms5848 KiB
4Hibás válasz195ms5876 KiB
5Hibás válasz202ms5916 KiB
6Hibás válasz172ms6000 KiB
7Futási hiba1ms316 KiB
subtask60/20
1Hibás válasz405ms11524 KiB
2Hibás válasz379ms11564 KiB
3Hibás válasz382ms11524 KiB
4Hibás válasz386ms11528 KiB
5Hibás válasz384ms11548 KiB
6Hibás válasz284ms11472 KiB
7Hibás válasz368ms11544 KiB
subtask70/20
1Hibás válasz173ms5916 KiB
2Hibás válasz179ms5932 KiB
3Hibás válasz188ms5868 KiB
4Hibás válasz143ms5916 KiB
5Hibás válasz190ms5804 KiB
6Hibás válasz187ms5916 KiB
7Hibás válasz145ms5892 KiB
8Hibás válasz188ms5896 KiB
9Hibás válasz190ms5940 KiB
10Hibás válasz197ms6096 KiB
11Hibás válasz216ms6560 KiB
12Hibás válasz239ms7160 KiB
13Hibás válasz287ms11468 KiB
14Hibás válasz342ms11448 KiB