QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#499720	#8271. Sequence	bachbeo2007	100 ✓	440ms	37196kb	C++23	1.2kb	2024-07-31 17:52:52	2024-07-31 17:52:52

Judging History

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

[2024-07-31 17:52:52]
评测

测评结果：100
用时：440ms
内存：37196kb

查看

[2024-07-31 17:52:52]
提交

answer

#include<bits/stdc++.h>
using namespace std;
const int maxn = 30005;
#define int long long
const int inf = 1e18;

int n,w[maxn];
vector<int> f[maxn];
map<vector<int>,int> mp;

int g(vector<int> x){
    if(x.empty()) return w[1]+w[2];
    if(mp.find(x)!=mp.end()) return mp[x];
    vector<int> c=x;
    int a=c.back();c.pop_back();

    int res=inf;
    for(int i:f[a]){
        int j=a/i;
        vector<int> nx=c;
        if(i>2) nx.push_back(i);
        if(j>2) nx.push_back(j);
        sort(nx.begin(),nx.end());
        nx.erase(unique(nx.begin(),nx.end()),nx.end());
        res=min(res,g(nx));
    }
    if(a>3) c.push_back(a-1);
    sort(c.begin(),c.end());
    c.erase(unique(c.begin(),c.end()),c.end());
    res=min(res,g(c));
    return mp[x]=res+w[a];
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> n;
    for(int i=1;i<=n;i++) cin >> w[i];
    for(int i=2;i<=n;i++) for(int j=i*i;j<=n;j+=i) f[j].push_back(i);

    cout << w[1] << '\n';
    if(n>=2) cout << w[1]+w[2] << '\n';
    if(n<=2) return 0;
    for(int i=3;i<=n;i++) cout << g({i}) << '\n';
    cout << '\n';
}

源文件, 语言: C++23

详细

Subtask #1:

score: 11

Accepted

Test #1:

score: 11

Accepted

time: 1ms

memory: 3544kb

input:

output:

result:

ok 10 lines

Test #2:

score: 11

Accepted

time: 0ms

memory: 3628kb

input:

output:

result:

ok 5 lines

Test #3:

score: 11

Accepted

time: 0ms

memory: 3528kb

input:

output:

result:

ok 5 lines

Test #4:

score: 11

Accepted

time: 0ms

memory: 3828kb

input:

output:

result:

ok 10 lines

Test #5:

score: 11

Accepted

time: 1ms

memory: 3604kb

input:

output:

result:

ok 10 lines

Test #6:

score: 11

Accepted

time: 1ms

memory: 3548kb

input:

output:

result:

ok 10 lines

Test #7:

score: 11

Accepted

time: 0ms

memory: 3632kb

input:

output:

result:

ok 10 lines

Test #8:

score: 11

Accepted

time: 0ms

memory: 3628kb

input:

output:

result:

ok 10 lines

Test #9:

score: 11

Accepted

time: 0ms

memory: 3828kb

input:

output:

result:

ok 9 lines

Test #10:

score: 11

Accepted

time: 0ms

memory: 3540kb

input:

output:

result:

ok 7 lines

Test #11:

score: 11

Accepted

time: 0ms

memory: 3752kb

input:

output:

10
52
53

result:

ok 3 lines

Subtask #2:

score: 10

Accepted

Test #12:

score: 10

Accepted

time: 0ms

memory: 3764kb

input:

1
1

output:

result:

ok single line: '1'

Test #13:

score: 10

Accepted

time: 0ms

memory: 3840kb

input:

output:

result:

ok 5 lines

Test #14:

score: 10

Accepted

time: 1ms

memory: 3640kb

input:

output:

result:

ok 300 lines

Test #15:

score: 10

Accepted

time: 0ms

memory: 3540kb

input:

output:

result:

ok 11 lines

Test #16:

score: 10

Accepted

time: 0ms

memory: 3928kb

input:

output:

result:

ok 299 lines

Subtask #3:

score: 10

Accepted

Dependency #2:

100%

Accepted

Test #17:

score: 10

Accepted

time: 0ms

memory: 3828kb

input:

1
1

output:

result:

ok single line: '1'

Test #18:

score: 10

Accepted

time: 0ms

memory: 3564kb

input:

output:

result:

ok 5 lines

Test #19:

score: 10

Accepted

time: 1ms

memory: 3700kb

input:

output:

result:

ok 300 lines

Test #20:

score: 10

Accepted

time: 0ms

memory: 3628kb

input:

output:

result:

ok 11 lines

Test #21:

score: 10

Accepted

time: 0ms

memory: 3716kb

input:

output:

result:

ok 299 lines

Test #22:

score: 10

Accepted

time: 1ms

memory: 3636kb

input:

output:

result:

ok 300 lines

Test #23:

score: 10

Accepted

time: 1ms

memory: 3712kb

input:

output:

result:

ok 300 lines

Test #24:

score: 10

Accepted

time: 1ms

memory: 3712kb

input:

output:

result:

ok 300 lines

Test #25:

score: 10

Accepted

time: 1ms

memory: 3864kb

input:

output:

result:

ok 300 lines

Test #26:

score: 10

Accepted

time: 1ms

memory: 3632kb

input:

output:

result:

ok 300 lines

Test #27:

score: 10

Accepted

time: 1ms

memory: 3864kb

input:

output:

result:

ok 300 lines

Test #28:

score: 10

Accepted

time: 1ms

memory: 3940kb

input:

output:

result:

ok 300 lines

Test #29:

score: 10

Accepted

time: 1ms

memory: 3572kb

input:

output:

result:

ok 300 lines

Subtask #4:

score: 9

Accepted

Dependency #2:

100%

Accepted

Test #30:

score: 9

Accepted

time: 0ms

memory: 3604kb

input:

1
1

output:

result:

ok single line: '1'

Test #31:

score: 9

Accepted

time: 0ms

memory: 3536kb

input:

output:

result:

ok 5 lines

Test #32:

score: 9

Accepted

time: 0ms

memory: 3648kb

input:

output:

result:

ok 300 lines

Test #33:

score: 9

Accepted

time: 0ms

memory: 3616kb

input:

output:

result:

ok 11 lines

Test #34:

score: 9

Accepted

time: 1ms

memory: 3644kb

input:

output:

result:

ok 299 lines

Test #35:

score: 9

Accepted

time: 1ms

memory: 3640kb

input:

output:

result:

ok 301 lines

Test #36:

score: 9

Accepted

time: 2ms

memory: 4280kb

input:

output:

result:

ok 1399 lines

Test #37:

score: 9

Accepted

time: 5ms

memory: 4568kb

input:

output:

result:

ok 1400 lines

Subtask #5:

score: 45

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Dependency #4:

100%

Accepted

Test #38:

score: 45

Accepted

time: 0ms

memory: 3560kb

input:

output:

result:

ok 10 lines

Test #39:

score: 45

Accepted

time: 0ms

memory: 3760kb

input:

output:

result:

ok 5 lines

Test #40:

score: 45

Accepted

time: 0ms

memory: 3548kb

input:

output:

result:

ok 5 lines

Test #41:

score: 45

Accepted

time: 0ms

memory: 3540kb

input:

output:

result:

ok 10 lines

Test #42:

score: 45

Accepted

time: 0ms

memory: 3840kb

input:

output:

result:

ok 10 lines

Test #43:

score: 45

Accepted

time: 0ms

memory: 3496kb

input:

output:

result:

ok 10 lines

Test #44:

score: 45

Accepted

time: 0ms

memory: 3600kb

input:

output:

result:

ok 10 lines

Test #45:

score: 45

Accepted

time: 0ms

memory: 3632kb

input:

output:

result:

ok 10 lines

Test #46:

score: 45

Accepted

time: 0ms

memory: 3568kb

input:

output:

result:

ok 9 lines

Test #47:

score: 45

Accepted

time: 0ms

memory: 3792kb

input:

output:

result:

ok 7 lines

Test #48:

score: 45

Accepted

time: 0ms

memory: 3536kb

input:

1
1

output:

result:

ok single line: '1'

Test #49:

score: 45

Accepted

time: 0ms

memory: 3840kb

input:

output:

result:

ok 5 lines

Test #50:

score: 45

Accepted

time: 1ms

memory: 3684kb

input:

output:

result:

ok 300 lines

Test #51:

score: 45

Accepted

time: 0ms

memory: 3632kb

input:

output:

result:

ok 11 lines

Test #52:

score: 45

Accepted

time: 1ms

memory: 3712kb

input:

output:

result:

ok 299 lines

Test #53:

score: 45

Accepted

time: 1ms

memory: 3904kb

input:

output:

result:

ok 301 lines

Test #54:

score: 45

Accepted

time: 5ms

memory: 4536kb

input:

output:

result:

ok 1399 lines

Test #55:

score: 45

Accepted

time: 5ms

memory: 4356kb

input:

output:

result:

ok 1400 lines

Test #56:

score: 45

Accepted

time: 32ms

memory: 7276kb

input:

output:

result:

ok 5000 lines

Test #57:

score: 45

Accepted

time: 8ms

memory: 4760kb

input:

output:

result:

ok 2047 lines

Test #58:

score: 45

Accepted

time: 25ms

memory: 7260kb

input:

output:

result:

ok 5000 lines

Test #59:

score: 45

Accepted

time: 28ms

memory: 7256kb

input:

output:

result:

ok 5000 lines

Test #60:

score: 45

Accepted

time: 25ms

memory: 7264kb

input:

output:

result:

ok 5000 lines

Test #61:

score: 45

Accepted

time: 24ms

memory: 7140kb

input:

output:

result:

ok 5000 lines

Test #62:

score: 45

Accepted

time: 28ms

memory: 7176kb

input:

output:

result:

ok 5000 lines

Test #63:

score: 45

Accepted

time: 28ms

memory: 7492kb

input:

output:

result:

ok 5000 lines

Test #64:

score: 45

Accepted

time: 25ms

memory: 7272kb

input:

output:

result:

ok 4999 lines

Test #65:

score: 45

Accepted

time: 0ms

memory: 3556kb

input:

output:

10
52
53

result:

ok 3 lines

Subtask #6:

score: 15

Accepted

Dependency #5:

100%

Accepted

Test #66:

score: 15

Accepted

time: 1ms

memory: 3612kb

input:

output:

result:

ok 10 lines

Test #67:

score: 15

Accepted

time: 0ms

memory: 3756kb

input:

output:

result:

ok 5 lines

Test #68:

score: 15

Accepted

time: 0ms

memory: 3620kb

input:

output:

result:

ok 5 lines

Test #69:

score: 15

Accepted

time: 0ms

memory: 3548kb

input:

output:

result:

ok 10 lines

Test #70:

score: 15

Accepted

time: 0ms

memory: 3528kb

input:

output:

result:

ok 10 lines

Test #71:

score: 15

Accepted

time: 0ms

memory: 3832kb

input:

output:

result:

ok 10 lines

Test #72:

score: 15

Accepted

time: 0ms

memory: 3796kb

input:

output:

result:

ok 10 lines

Test #73:

score: 15

Accepted

time: 0ms

memory: 3624kb

input:

output:

result:

ok 10 lines

Test #74:

score: 15

Accepted

time: 0ms

memory: 3552kb

input:

output:

result:

ok 9 lines

Test #75:

score: 15

Accepted

time: 0ms

memory: 3492kb

input:

output:

result:

ok 7 lines

Test #76:

score: 15

Accepted

time: 0ms

memory: 3840kb

input:

1
1

output:

result:

ok single line: '1'

Test #77:

score: 15

Accepted

time: 0ms

memory: 3600kb

input:

output:

result:

ok 5 lines

Test #78:

score: 15

Accepted

time: 1ms

memory: 3936kb

input:

output:

result:

ok 300 lines

Test #79:

score: 15

Accepted

time: 0ms

memory: 3632kb

input:

output:

result:

ok 11 lines

Test #80:

score: 15

Accepted

time: 1ms

memory: 3724kb

input:

output:

result:

ok 299 lines

Test #81:

score: 15

Accepted

time: 1ms

memory: 3708kb

input:

output:

result:

ok 301 lines

Test #82:

score: 15

Accepted

time: 5ms

memory: 4280kb

input:

output:

result:

ok 1399 lines

Test #83:

score: 15

Accepted

time: 5ms

memory: 4284kb

input:

output:

result:

ok 1400 lines

Test #84:

score: 15

Accepted

time: 29ms

memory: 7216kb

input:

output:

result:

ok 5000 lines

Test #85:

score: 15

Accepted

time: 8ms

memory: 4828kb

input:

output:

result:

ok 2047 lines

Test #86:

score: 15

Accepted

time: 28ms

memory: 7268kb

input:

output:

result:

ok 5000 lines

Test #87:

score: 15

Accepted

time: 25ms

memory: 7148kb

input:

output:

result:

ok 5000 lines

Test #88:

score: 15

Accepted

time: 28ms

memory: 7144kb

input:

output:

result:

ok 5000 lines

Test #89:

score: 15

Accepted

time: 25ms

memory: 7180kb

input:

output:

result:

ok 5000 lines

Test #90:

score: 15

Accepted

time: 29ms

memory: 7280kb

input:

output:

result:

ok 5000 lines

Test #91:

score: 15

Accepted

time: 24ms

memory: 7284kb

input:

output:

result:

ok 5000 lines

Test #92:

score: 15

Accepted

time: 25ms

memory: 7124kb

input:

output:

result:

ok 4999 lines

Test #93:

score: 15

Accepted

time: 165ms

memory: 19464kb

input:

output:

result:

ok 16383 lines

Test #94:

score: 15

Accepted

time: 417ms

memory: 37072kb

input:

output:

result:

ok 30000 lines

Test #95:

score: 15

Accepted

time: 420ms

memory: 37196kb

input:

output:

result:

ok 30000 lines

Test #96:

score: 15

Accepted

time: 440ms

memory: 37192kb

input:

output:

result:

ok 30000 lines

Test #97:

score: 15

Accepted

time: 434ms

memory: 37176kb

input:

output:

result:

ok 30000 lines

Test #98:

score: 15

Accepted

time: 431ms

memory: 37180kb

input:

output:

result:

ok 30000 lines

Test #99:

score: 15

Accepted

time: 439ms

memory: 37180kb

input:

output:

result:

ok 30000 lines

Test #100:

score: 15

Accepted

time: 433ms

memory: 37184kb

input:

output:

result:

ok 30000 lines

Test #101:

score: 15

Accepted

time: 0ms

memory: 3596kb

input:

output:

10
52
53

result:

ok 3 lines