Submission #1194369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194369		Petrix	Sails (IOI07_sails)	C++20	25 / 100	1095 ms	131072 KiB

sails

#include <iostream>

using namespace std;

#define int long long

int frv[100001],rasp;
int k[100001];
int h[100001];
void back_track(int pole,int kth,int poz,int sum){
    if(pole==0){
        rasp=min(rasp,sum);
        return;
    }
    if(kth>k[pole]){
        back_track(pole-1,1,1,sum);
        return ;
    }
    int i;
    for(i=poz;i<=h[pole]-(k[pole]-kth);i++){
        sum+=frv[i];frv[i]++;
        back_track(pole,kth+1,i+1,sum);
        frv[i]--;sum-=frv[i];
    }
}



signed main()
{
    int n,i;rasp=1e18;
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>h[i]>>k[i];
    }
    back_track(n,1,1,0);
    cout<<rasp;
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10