QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#606900#8936. Team ArrangementAAA___#TL 2ms3724kbC++202.3kb2024-10-03 12:55:112024-10-03 12:55:14

Judging History

This is the latest submission verdict.

  • [2024-10-03 12:55:14]
  • Judged
  • Verdict: TL
  • Time: 2ms
  • Memory: 3724kb
Show
  • [2024-10-03 12:55:11]
  • Submitted

answer

#include<iostream>
#include<algorithm>
#include<stack>
#include<set>
#include<unordered_set>
#include<queue>
#include<deque>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<map>
#include<string>
#include<vector>
#include<array>
#include<functional>
using namespace std;
typedef long long ll;
ll highbit(ll x){
    ll ans=2;
    int num=1;
    while(x){
        x>>=2;
        ans<<=2;
        num++;
    }
    return num;
}
ll lowbit(ll x){
    return x&(-x);
}
long long max(long long a,long long b){
    return a>b?a:b;
}
long long min(long long a,long long b){
    return a>b?b:a;
}
ll gcd(ll x,ll y)
{
    if(y==1)
        return x;
    return gcd(y,x%y);
}
const int maxn=100;
ll w[maxn];
ll L[maxn];
ll R[maxn];
ll ans=-1e17;
array<ll,61> num;
array<ll,61> diff;
bool flag=0;
void dfs(array<ll,61>& num,array<ll,61>& diff,int pos,int n){
    if(pos==n+1){
        ll buff=0;
        for(int i=1;i<=n;i++){
            if(num[i]%i!=0){
                return;
            }
        }
        flag=true;
        for(int i=1;i<=n;i++){
            buff+=w[i]*(num[i]/i);
        }
        ans=max(ans,buff);
        return;
    }
    for(int i=1;i<=n;i++){
        if((num[i]%i)==0){
            continue;
        }
        if(diff[i]<(i-(num[i]%i))){
            return;
        }
    }
    for(int i=L[pos];i<=R[pos];i++){
        if(diff[i]>=(i-(num[i]%i))){
            for(int j=L[pos];j<=R[pos];j++){
                diff[j]--;
            }
            num[i]++;
            dfs(num,diff,pos+1,n);
            num[i]--;
            for(int j=L[pos];j<=R[pos];j++){
                diff[j]++;
            }
        }
    }
    return ;
}
void solve() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        diff[i]=num[i]=0;
    }
    for(int i=1;i<=n;i++){
        cin>>L[i]>>R[i];
        for(int j=L[i];j<=R[i];j++){
            diff[j]++;
        }
    }
    for(int i=1;i<=n;i++){
        cin>>w[i];
    }
    dfs(num,diff,1,n);
    if(!flag){
        cout<<"impossible"<<endl;
    }else{
        cout<<ans<<endl;
    }
    return;
}
int main(void){
    unsigned int t;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.in","r",stdin);
    //cin>>t;
    t=1;
    while(t--){
        solve();
    }
    return 0;
}
源文件, 语言: C++20

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3652kb

input:

3
2 3
1 2
2 2
4 5 100

output:

9

result:

ok single line: '9'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3716kb

input:

3
1 3
3 3
2 3
1 1 100

output:

100

result:

ok single line: '100'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

2
1 1
2 2
1 1

output:

impossible

result:

ok single line: 'impossible'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

3
2 3
1 2
2 2
-100 -200 100000

output:

-300

result:

ok single line: '-300'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

9
1 4
2 5
3 4
1 5
1 1
2 5
3 5
1 3
1 1
1 1 1 1 1 1 1 1 1

output:

6

result:

ok single line: '6'

Test #6:

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

input:

14
3 3
1 2
2 3
2 3
2 3
1 1
2 3
1 3
3 3
1 3
1 3
1 2
2 3
1 3
-9807452 -9610069 4156341 2862447 6969109 -7245265 -2653530 -5655094 6467527 -6872459 3971784 7312155 9766298 -2719573

output:

-16558567

result:

ok single line: '-16558567'

Test #7:

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

input:

14
1 2
1 4
2 3
3 5
4 5
2 5
2 4
2 4
1 2
3 4
1 5
2 4
1 1
4 5
-13763 -7354207 1096407 -9063321 -4824546 -6275546 1258145 -5272834 -8631107 3581157 2320771 -7714508 8446625 -6816167

output:

-2673021

result:

ok single line: '-2673021'

Test #8:

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

input:

14
2 3
4 4
1 7
3 6
3 4
1 1
1 4
4 7
3 7
1 7
2 3
6 6
1 1
3 6
2923142 1686477 640352 2848353 9202543 -4441381 4866381 -3610520 8124124 -1372894 1111310 -7538627 466143 9937961

output:

5939733

result:

ok single line: '5939733'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3716kb

input:

14
1 7
1 2
8 8
1 1
7 8
6 9
7 8
1 4
6 9
3 3
1 1
3 7
5 8
4 8
-7139089 6365816 -9893288 5936146 -2803918 -4961415 1495365 -2564851 -2630365 -8608883 5813455 -4005459 -8844054 6703783

output:

impossible

result:

ok single line: 'impossible'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

14
6 13
3 7
2 13
6 8
4 5
12 13
3 10
4 11
2 14
3 4
5 13
10 14
10 14
3 12
-8599727 -1496394 855072 -7439122 -5170228 8009298 -250221 5841035 2949765 7166358 -3516548 -6851737 8173765 -917122

output:

impossible

result:

ok single line: 'impossible'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3716kb

input:

60
21 34
13 34
48 49
31 42
5 6
16 30
1 25
35 37
3 14
3 32
25 54
2 41
24 44
27 52
26 55
8 35
31 47
41 42
4 35
53 59
13 19
11 51
36 48
5 59
40 44
28 50
5 51
37 53
50 60
14 50
22 58
20 50
20 21
5 20
19 55
5 45
19 35
7 29
5 53
25 33
19 51
37 41
13 29
12 24
13 40
10 22
1 5
22 32
14 42
11 41
16 60
35 43
3...

output:

impossible

result:

ok single line: 'impossible'

Test #12:

score: -100
Time Limit Exceeded

input:

60
4 11
1 7
8 24
2 18
11 26
6 18
5 26
5 11
6 21
17 30
9 22
1 29
7 14
9 18
23 26
3 28
3 14
4 16
7 18
2 3
8 8
10 20
8 29
5 28
5 7
16 19
16 18
8 11
5 28
12 21
8 20
8 27
9 23
15 28
1 4
6 27
10 15
10 20
2 7
4 21
9 23
23 25
20 23
19 29
16 25
12 15
3 27
3 9
1 26
9 11
12 14
14 24
16 22
7 7
9 26
24 29
3 27
1...

output:

result:
English 繁體中文 简体中文

服务器时间: 2025-02-06 00:00:10 | 开源项目