Submission #1309969

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309969		quollcucumber`	Netrpeljivost (COI23_netrpeljivost)	C++20	0 / 100	0 ms	332 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
int minval, total, n;
int anti[2048][2048];
int arr[2048];
int calctotal(int point) {
    int num = 0;
    if(point != 0) {
        num += anti[arr[point - 1]][arr[point]];
    }
    if(point != n-1) {
        num += anti[arr[point]][arr[point+1]];
    }
    return num;
}
void dp(int l, int r) {
    if(l + 1 == r) return;
    int mid = (l + r )/ 2;
    dp(l, mid);
    dp(mid, r);
    int newtotal = total;
    newtotal -= calctotal(l);
    newtotal -= calctotal(r-1);
    arr[l] = r-1;
    arr[r-1] = l;
    newtotal += calctotal(l);
    newtotal += calctotal(r-1);
    arr[l] = l;
    arr[r-1] = r-1;
    minval = min(minval, newtotal);
}
signed main(){
    for(int i = 0; i < 2048; i++) arr[i] = i;
    cin >> n;
    total = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> anti[i][j];
        }
    }
    for(int i =0; i < n-1; i++) {
        total += anti[i][i+1];
    }
    minval = total;
    dp(0, n);
    cout<<minval<<'\n';
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 17
• Subtask 3: 0 / 32
• Subtask 4: 0 / 41