QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#408976#7762. 数据库HuTao80 244ms4280kbC++142.7kb2024-05-11 14:10:332024-05-11 14:10:34

Judging History

你现在查看的是最新测评结果

  • [2024-05-11 14:10:34]
  • 评测
  • 测评结果:80
  • 用时:244ms
  • 内存:4280kb
  • [2024-05-11 14:10:33]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

// struct CLOCK{
//     int ST;
//     CLOCK() {ST = clock();}
//     ~CLOCK() {cerr << "Time : " << clock() - ST << endl;}
// };
// CLOCK ACOIPP;

const int N = 5015;

int n, m, q, k, w[N], pre[N];
int res;

template <const int N, const int M>
struct SSP{
    int s, t;
    struct Edge{
        int ne, en, c, w;
    }e[M];
    int la[N], idx = 1;
    int dis[N], pre[N], vis[N], q[N], hh, tt;
    int MinCost, Step;

    inline void AddEdge(int a, int b, int c, int d)
    {
        e[ ++ idx] = {la[a], b, c, d};
        la[a] = idx;
    }
    inline void Add(int a, int b, int c, int d)
    {
        // printf("#%d %d %d %d\n", a, b, c, d);
        AddEdge(a, b, c, d);
        AddEdge(b, a, 0, -d);
    }
    inline bool SPFA()
    {
        memset(dis, -0x3f, sizeof dis), dis[s] = 0;
        hh = 0, tt = 1, q[0] = s;
        int CNT = 0;
        while(hh != tt)
        {
            int u = q[hh ++ ];
            (hh == N) && (hh = 0);
            vis[u] = 0;
            for(int i = la[u]; i; i = e[i].ne)
            {
                CNT ++ ;
                int v = e[i].en;
                if(e[i].c && dis[v] < dis[u] + e[i].w)
                {
                    dis[v] = dis[u] + e[i].w;
                    pre[v] = i;
                    if(!vis[v])
                    {
                        q[tt ++ ] = v;
                        (tt == N) && (tt = 0);
                        vis[v] = 1;
                    }
                }
            }
            if(CNT >= 1000000 && Step > 3) break ;
        }

        if(dis[t] <= 0) return 0;
        int c = 1e9;
        for(int u = t; u != s; u = e[pre[u] ^ 1].en)
            c = min(c, e[pre[u]].c);
        MinCost += c * dis[t];
        for(int u = t; u != s; u = e[pre[u] ^ 1].en)
        {
            e[pre[u]].c -= c;
            e[pre[u] ^ 1].c += c;
        }
        return 1;
    }
    inline int Work()
    {
        while(SPFA()) Step ++ ;
        return MinCost;
    }
};
SSP<N, N * 4> G;

int main()
{
    // freopen("db.in", "r", stdin);
    // freopen("db.out", "w", stdout);

    scanf("%d%d%d", &n, &m, &q), m -- ;
    G.s = 0, G.t = q + 1;
    G.Add(0, 1, m, 0);
    for(int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    for(int i = 1; i <= q; i ++ )
    {
        scanf("%d", &k);
        if(pre[k])
        {
            if(pre[k] != i - 1)
            {
                res += w[k];
                G.Add(pre[k] + 1, i, 1, w[k]);
            }
        }
        else res += w[k];
        pre[k] = i;
        G.Add(i, i + 1, m, 0);
    }
    res -= G.Work();
    printf("%d\n", res);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 137ms
memory: 4272kb

input:

10 3 5000
23077 34848 88221 8067 83132 62621 41320 69146 32971 27594
2 7 5 3 9 6 1 9 4 8 1 8 8 3 6 9 1 7 5 5 6 8 1 3 10 6 8 7 10 2 1 2 6 7 5 5 9 5 7 10 10 6 6 7 2 4 3 1 10 10 5 1 1 6 1 2 8 9 2 5 10 1 10 7 5 5 10 5 2 5 6 10 9 5 6 3 5 3 6 5 7 4 1 5 8 1 1 9 7 1 1 2 1 8 6 2 9 8 4 2 5 4 5 2 10 4 3 6 9 7 ...

output:

100598924

result:

ok single line: '100598924'

Test #2:

score: 0
Accepted
time: 189ms
memory: 4280kb

input:

10 4 5000
54224 55364 32836 46635 99179 26033 49587 15072 63093 94302
4 7 8 4 1 2 6 3 1 1 6 10 5 7 2 9 3 9 1 5 7 3 8 4 7 2 5 3 5 4 1 6 4 10 4 10 8 1 5 7 9 7 9 1 6 1 10 10 10 5 1 1 3 5 10 1 8 8 6 8 8 10 6 9 7 6 1 1 5 3 10 8 6 5 8 7 5 8 4 8 8 1 8 6 4 5 8 10 7 6 7 2 10 7 10 10 3 1 3 5 5 7 3 2 5 3 1 7 6...

output:

85562058

result:

ok single line: '85562058'

Test #3:

score: 0
Accepted
time: 238ms
memory: 4272kb

input:

10 5 5000
8091 5917 35634 83114 46741 61842 48134 41606 63881 20560
8 7 9 5 1 4 10 9 10 9 8 5 5 7 5 1 5 9 4 1 4 7 9 4 10 4 4 2 9 1 5 1 2 6 10 1 5 4 5 3 3 1 6 7 5 7 10 2 5 8 2 9 3 5 3 1 2 4 5 10 4 4 10 4 8 2 8 6 4 1 3 6 8 2 6 2 2 5 9 4 2 8 3 10 8 7 2 1 10 6 5 8 2 8 9 3 9 5 6 6 7 2 7 3 10 9 10 2 4 7 2...

output:

43892491

result:

ok single line: '43892491'

Subtask #2:

score: 20
Accepted

Test #4:

score: 20
Accepted
time: 74ms
memory: 4192kb

input:

10 2 5000
65644 5214 85000 40719 98071 56616 35404 16019 96748 89032
5 9 6 1 3 6 8 10 2 9 1 10 5 9 9 9 2 7 7 7 7 10 5 1 3 10 4 2 5 5 2 8 3 2 1 3 3 6 2 4 5 5 2 5 2 3 4 2 10 1 4 6 10 9 6 4 9 10 5 3 9 7 7 2 1 9 5 8 8 4 8 8 4 5 6 1 3 4 8 10 4 3 6 6 9 2 5 2 8 5 10 4 7 10 3 9 3 2 9 3 10 7 1 3 9 9 3 5 1 3 ...

output:

173524192

result:

ok single line: '173524192'

Test #5:

score: 0
Accepted
time: 45ms
memory: 4280kb

input:

100 2 5000
49570 6371 37107 2261 33457 98048 84700 76277 32602 53831 20995 86351 57905 93492 65198 80688 44394 48442 57924 88655 16250 11904 21033 99426 59241 71456 7697 85276 81310 49884 64543 72091 63969 23936 88032 62420 42269 76663 37639 16930 61480 97674 38809 77434 25043 46618 93378 74399 1031...

output:

231972847

result:

ok single line: '231972847'

Test #6:

score: 0
Accepted
time: 15ms
memory: 4184kb

input:

1000 2 5000
40824 4748 88829 17859 98470 82824 82849 16663 96731 71333 73050 75770 22643 62690 87789 72306 46178 68415 85222 18729 54074 53251 45445 35978 1417 85067 89297 42145 43426 1108 28947 87941 49299 51501 80512 41395 71615 26966 60841 87838 41260 59483 31968 54392 50188 65874 275 38593 32941...

output:

241831233

result:

ok single line: '241831233'

Subtask #3:

score: 20
Accepted

Test #7:

score: 20
Accepted
time: 1ms
memory: 4036kb

input:

5000 15 400
34145 93322 29976 7963 53362 50640 10859 94528 13329 49980 18826 50286 60155 79748 73253 18329 5216 83079 48220 98825 46592 76855 14037 19859 80960 4461 377 70496 28092 99806 5355 27013 92051 95231 65553 32365 3862 89764 86063 93033 12754 68996 38965 52942 69948 34370 3023 52079 16066 57...

output:

19341503

result:

ok single line: '19341503'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3884kb

input:

5000 15 400
68511 70579 96844 20943 72871 28340 68790 60294 76760 12623 80406 65418 37942 2849 76307 28818 18555 42151 94506 78241 15350 11345 76323 21860 22703 31009 24763 71007 60858 53746 28720 5027 72512 39122 55299 41675 88475 94331 78711 3464 80345 69031 98746 14792 97862 97255 5853 92742 9096...

output:

19515326

result:

ok single line: '19515326'

Test #9:

score: 0
Accepted
time: 1ms
memory: 3976kb

input:

5000 15 400
18305 15347 86331 37503 78391 3378 82447 51150 49032 2422 47659 20516 18666 16520 27948 17865 45842 66799 35584 75288 46358 21654 30233 25291 44810 27579 93986 15174 56012 48286 66826 93615 77979 40669 17262 77857 82134 50752 19642 77961 55856 68600 60598 33035 94214 17392 16736 21460 58...

output:

18253485

result:

ok single line: '18253485'

Subtask #4:

score: 20
Accepted

Test #10:

score: 20
Accepted
time: 9ms
memory: 4044kb

input:

10 5 1000
86764 81108 88408 93029 87155 18790 28170 29349 81866 77109
8 7 10 7 2 7 1 8 4 10 9 10 4 1 7 1 9 9 1 6 6 1 9 6 7 1 8 10 1 7 9 1 1 9 7 10 8 5 5 1 2 3 10 6 2 6 2 6 1 2 7 8 5 6 10 2 9 8 2 6 8 5 10 8 1 10 4 6 5 6 3 8 1 3 5 2 2 7 2 4 5 5 8 2 4 1 3 6 8 2 2 3 1 8 1 5 8 6 9 7 7 3 7 9 8 9 9 7 5 3 6...

output:

15248002

result:

ok single line: '15248002'

Test #11:

score: 0
Accepted
time: 12ms
memory: 4076kb

input:

10 10 1000
57793 91210 18011 676 38391 78527 56352 69343 95947 5616
5 8 4 5 10 6 1 7 3 10 2 7 1 9 5 3 5 8 3 8 7 10 2 10 6 1 4 3 6 10 6 3 8 4 3 9 1 6 10 3 10 1 6 2 9 9 3 5 8 8 3 9 1 5 9 9 3 3 7 9 2 4 1 9 8 3 1 2 8 9 10 9 4 3 10 5 4 4 8 6 6 9 3 3 2 3 7 2 3 3 10 4 5 5 6 4 2 5 10 1 2 6 9 8 7 9 4 8 2 1 2...

output:

511866

result:

ok single line: '511866'

Test #12:

score: 0
Accepted
time: 12ms
memory: 4012kb

input:

10 15 1000
19536 14188 62086 25660 67447 48774 97871 17167 8671 85361
3 5 2 6 4 6 10 5 7 6 10 8 1 9 5 7 5 5 2 10 7 10 8 6 3 4 2 2 8 9 6 10 9 10 10 9 6 1 7 2 1 10 8 10 3 9 1 8 10 4 6 9 9 8 1 5 2 10 9 1 3 6 5 6 2 5 3 9 6 5 6 10 5 6 10 4 6 6 8 8 9 5 2 10 1 10 7 4 2 6 10 5 6 2 3 1 3 9 8 3 9 7 7 7 2 6 7 ...

output:

446761

result:

ok single line: '446761'

Test #13:

score: 0
Accepted
time: 2ms
memory: 3904kb

input:

100 5 1000
95646 33117 46458 52069 38647 38645 60235 93897 41039 35835 49580 92470 5371 6812 38049 9178 50163 92322 9735 27037 58888 49095 68473 5472 1644 94513 50597 10246 96329 51334 1986 79907 89526 10771 29923 55249 59048 91934 46853 79352 85644 57708 57300 20536 70782 61882 58712 97314 45686 55...

output:

36018137

result:

ok single line: '36018137'

Test #14:

score: 0
Accepted
time: 7ms
memory: 3996kb

input:

100 10 1000
36326 35981 96633 82565 65884 23199 50344 49682 96971 42033 2351 31928 50056 73426 36217 89994 30603 27971 17757 19901 99501 35915 27895 26451 91714 36134 94294 19114 22490 97680 48272 80639 24603 93000 28420 7595 7314 52546 12258 58666 88422 29237 69223 41046 13515 72493 26486 34554 239...

output:

30951978

result:

ok single line: '30951978'

Test #15:

score: 0
Accepted
time: 12ms
memory: 4080kb

input:

100 15 1000
60259 28844 6884 35222 45974 11055 13021 13966 14853 85552 12283 29760 50104 63448 84364 1684 99886 31837 61724 84415 28292 81814 31562 60077 93784 1729 1602 56374 19276 89781 13359 78765 97380 34118 39756 12254 61197 53500 95962 61254 16553 24467 58101 53482 65199 75076 67326 92045 306 ...

output:

26014456

result:

ok single line: '26014456'

Test #16:

score: 0
Accepted
time: 2ms
memory: 4012kb

input:

1000 5 1000
84587 68464 19119 74315 48972 23581 58263 43666 21662 5458 47594 18617 52236 24283 45998 66734 8501 94413 31981 77247 50069 95649 21536 8055 62698 98164 14074 22987 14525 12396 7681 17830 97091 88885 86419 1067 92977 54999 33673 9550 67710 98546 82017 17583 667 36168 61540 74015 42193 48...

output:

45688268

result:

ok single line: '45688268'

Test #17:

score: 0
Accepted
time: 3ms
memory: 4072kb

input:

1000 10 1000
24129 67704 68122 93372 94874 19813 14041 20830 97805 57074 99877 64455 80825 93755 98668 89675 35445 42895 74964 71326 43884 8123 1767 83698 2892 77832 21668 85066 17440 49874 77903 22427 45669 41174 40029 27379 61235 13563 4313 90065 99573 45555 19683 39486 76606 30438 34528 180 83016...

output:

44994110

result:

ok single line: '44994110'

Test #18:

score: 0
Accepted
time: 5ms
memory: 4000kb

input:

1000 15 1000
59991 63683 65484 87716 79869 15955 13746 80474 77381 51499 17028 13036 18275 82716 12845 66038 16310 66787 28778 73107 90796 63216 85094 24799 99979 96956 35994 21067 81494 75695 91088 34745 82075 27522 293 67267 51879 50823 80429 54323 21127 60258 40463 26950 69326 7049 39530 62048 23...

output:

39885004

result:

ok single line: '39885004'

Subtask #5:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #19:

score: 20
Accepted
time: 220ms
memory: 4260kb

input:

10 5 5000
95311 97197 20634 42609 6109 19539 52553 34009 78555 1142
1 2 4 4 5 8 9 1 1 6 8 3 5 7 1 10 5 1 3 3 10 6 3 6 2 7 9 8 8 3 4 3 7 4 5 5 4 10 5 10 10 9 3 8 6 1 10 5 2 3 7 8 7 8 1 1 5 9 7 4 1 4 7 6 5 8 1 5 6 10 10 3 4 3 9 7 7 9 7 7 9 10 9 5 6 8 4 8 5 2 1 2 1 1 3 10 6 8 5 8 2 1 7 9 2 3 10 3 5 7 6...

output:

39375079

result:

ok single line: '39375079'

Test #20:

score: -20
Wrong Answer
time: 244ms
memory: 4188kb

input:

10 10 5000
98273 81150 13203 63792 62989 68848 18153 51586 86054 21067
6 5 4 2 7 4 7 3 6 8 10 10 3 6 8 2 6 3 4 3 10 10 4 6 2 1 3 9 3 3 2 9 5 10 7 7 4 6 10 4 4 4 10 2 6 4 1 4 2 10 10 9 9 9 7 7 6 10 3 5 7 5 2 1 2 3 10 8 5 8 3 3 3 5 7 10 2 9 9 2 5 4 3 10 3 3 1 6 3 4 6 3 7 3 1 2 9 1 1 5 6 6 2 2 8 3 6 2 ...

output:

61060332

result:

wrong answer 1st lines differ - expected: '565115', found: '61060332'