oj.uz

답안 #1013640

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1013640 2024-07-03T18:10:39 Z amine_aroua Netrpeljivost (COI23_netrpeljivost) C++17
27 / 100
 1500 ms 6228 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
using namespace std;
#define intt long long
#define pb push_back
vector<vector<int>> mat;
int n ;
const intt INF = 1e18;
vector<map<pair<int ,int> , intt>> dp;
intt solve(int node ,int fr , int bk ,int l , int r)
{
    if(dp[node].count({fr , bk}))
        return dp[node][{fr , bk}];
    if(l + 1 == r)
    {
        return mat[fr][bk];
    }
    int m = (l + r)/2;
    intt ans = INF;
    if(l <= fr && fr <= m && m + 1 <= bk && bk <= r)
    {
        int L1 = l , R1 = (m + l)/2;
        int L2 = m + 1 , R2 = (m + 1 + r)/2;
        if(L1 <= fr&& fr <= R1 )
        {
            L1 = R1 + 1;
            R1 = m;
        }
        if(L2 <= bk && bk <= R2)
        {
            L2 = R2 + 1;
            R2 = r;
        }
        for(int v1 = L1 ; v1 <= R1 ;v1++)
        {
            for(int v2 = L2; v2 <= R2 ; v2++)
            {
                ans = min(ans , solve(2*node , fr , v1 , l , m) + solve(2*node + 1 , v2 , bk , m + 1 , r) + mat[v1][v2]);
            }
        }
    }
    else if(l <= bk && bk <= m && m + 1 <= fr && fr <= r)
    {
        int L1 = l , R1 = (m + l)/2;
        int L2 = m + 1 , R2 = (m + 1 + r)/2;
        if(L1 <= bk&& bk <= R1 )
        {
            L1 = R1 + 1;
            R1 = m;
        }
        if(L2 <= fr && fr <= R2)
        {
            L2 = R2 + 1;
            R2 = r;
        }
        for(int v1 = L1 ; v1 <= R1 ; v1++)
        {
            if(v1 == bk)
                continue;
            for(int v2 = L2 ; v2 <= R2 ; v2++)
            {
                if(v2 == fr)
                    continue;
                ans = min(ans , solve(2*node , v1 , bk , l , m) + solve(2*node + 1 , fr , v2 , m + 1 , r) + mat[v1][v2]);
            }
        }
    }
    return dp[node][{fr , bk}] = ans;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    mat = vector<vector<int>> (n , vector<int>(n));
    for(int i = 0 ; i < n ; i++)
    {
        for(int j = 0 ; j < n ; j++)
        {
            cin>>mat[i][j];
        }
    }
    if(n == 1)
    {
        cout<<0<<'\n';
        return 0;
    }
    dp.assign(2*n , map<pair<int ,int> , intt>());
    intt ans = INF;
    int l = 0 , r = n - 1;
    int m = (l  + r)/2;
    for(int fr = l ; fr <= m ; fr++)
    {
        for(int bk = m + 1 ; bk <= r ; bk++)
        {
            ans = min({ans , solve(1 , fr , bk , l , r) , solve(1 , bk , fr , l , r)});
        }
    }
    cout<<ans<<'\n';
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 904 ms 1464 KB Output is correct
22 Correct 903 ms 1620 KB Output is correct
23 Correct 861 ms 1532 KB Output is correct
24 Correct 67 ms 604 KB Output is correct
25 Correct 57 ms 636 KB Output is correct
26 Correct 909 ms 1660 KB Output is correct
27 Correct 840 ms 1620 KB Output is correct
28 Correct 832 ms 1436 KB Output is correct
29 Correct 831 ms 1488 KB Output is correct
30 Correct 862 ms 1484 KB Output is correct
31 Correct 837 ms 1544 KB Output is correct
32 Correct 884 ms 1616 KB Output is correct
33 Correct 874 ms 1708 KB Output is correct
34 Correct 891 ms 1564 KB Output is correct
35 Correct 871 ms 1876 KB Output is correct
36 Correct 886 ms 1648 KB Output is correct
37 Correct 820 ms 1644 KB Output is correct
38 Correct 839 ms 1672 KB Output is correct
39 Correct 836 ms 1616 KB Output is correct
40 Correct 860 ms 1644 KB Output is correct

Subtask #3
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 904 ms 1464 KB Output is correct
22 Correct 903 ms 1620 KB Output is correct
23 Correct 861 ms 1532 KB Output is correct
24 Correct 67 ms 604 KB Output is correct
25 Correct 57 ms 636 KB Output is correct
26 Correct 909 ms 1660 KB Output is correct
27 Correct 840 ms 1620 KB Output is correct
28 Correct 832 ms 1436 KB Output is correct
29 Correct 831 ms 1488 KB Output is correct
30 Correct 862 ms 1484 KB Output is correct
31 Correct 837 ms 1544 KB Output is correct
32 Correct 884 ms 1616 KB Output is correct
33 Correct 874 ms 1708 KB Output is correct
34 Correct 891 ms 1564 KB Output is correct
35 Correct 871 ms 1876 KB Output is correct
36 Correct 886 ms 1648 KB Output is correct
37 Correct 820 ms 1644 KB Output is correct
38 Correct 839 ms 1672 KB Output is correct
39 Correct 836 ms 1616 KB Output is correct
40 Correct 860 ms 1644 KB Output is correct
41 Execution timed out 1535 ms 6228 KB Time limit exceeded
42 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 904 ms 1464 KB Output is correct
22 Correct 903 ms 1620 KB Output is correct
23 Correct 861 ms 1532 KB Output is correct
24 Correct 67 ms 604 KB Output is correct
25 Correct 57 ms 636 KB Output is correct
26 Correct 909 ms 1660 KB Output is correct
27 Correct 840 ms 1620 KB Output is correct
28 Correct 832 ms 1436 KB Output is correct
29 Correct 831 ms 1488 KB Output is correct
30 Correct 862 ms 1484 KB Output is correct
31 Correct 837 ms 1544 KB Output is correct
32 Correct 884 ms 1616 KB Output is correct
33 Correct 874 ms 1708 KB Output is correct
34 Correct 891 ms 1564 KB Output is correct
35 Correct 871 ms 1876 KB Output is correct
36 Correct 886 ms 1648 KB Output is correct
37 Correct 820 ms 1644 KB Output is correct
38 Correct 839 ms 1672 KB Output is correct
39 Correct 836 ms 1616 KB Output is correct
40 Correct 860 ms 1644 KB Output is correct
41 Execution timed out 1535 ms 6228 KB Time limit exceeded
42 Halted 0 ms 0 KB -