QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#46822	#976. GPA	Ufowoqqqo	AC ✓	35ms	67652kb	C++	833b	2022-09-01 23:31:46	2022-09-01 23:31:48

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2022-09-01 23:31:48]
评测

测评结果：AC
用时：35ms
内存：67652kb

查看

[2022-09-01 23:31:46]
提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 4040;
const int INF = 0x3f3f3f3f;

int a[N], b[N];
int dp[N][N];

void update(int &a, int b)
{
    if(b < a)
        a = b;
}

int main()
{
    int n;
    int i, j;
    int w;

    scanf("%d", &n);
    for(i = 1; i <= n; i ++)
        scanf("%d%d", &a[i], &b[i]);

    memset(dp, 0x3f, sizeof dp);
    dp[0][0] = 0;
    for(i = 1; i <= n; i ++)
        for(j = 0; j < i; j ++)
        {
            w = dp[i - 1][j];
            update(dp[i][j + ((i - 1) * a[i] >= w)], w + a[i]);
            update(dp[i][j + ((i - 1) * b[i] >= w)], w + b[i]);
        }

    for(i = n; i >= 0; i --)
        if(dp[n][i] < INF)
        {
            printf("%d\n", n - i);
            break;
        }

    return 0;
}

源文件, 语言: C++

詳細信息

Test #1:

score: 100

Accepted

time: 4ms

memory: 67568kb

input:

output:

result:

ok 1 number(s): "1"

Test #2:

score: 0

Accepted

time: 16ms

memory: 67548kb

input:

output:

result:

ok 1 number(s): "31"

Test #3:

score: 0

Accepted

time: 16ms

memory: 67488kb

input:

output:

result:

ok 1 number(s): "44"

Test #4:

score: 0

Accepted

time: 16ms

memory: 67488kb

input:

output:

result:

ok 1 number(s): "40"

Test #5:

score: 0

Accepted

time: 11ms

memory: 67516kb

input:

output:

result:

ok 1 number(s): "56"

Test #6:

score: 0

Accepted

time: 4ms

memory: 67592kb

input:

output:

result:

ok 1 number(s): "50"

Test #7:

score: 0

Accepted

time: 15ms

memory: 67592kb

input:

output:

result:

ok 1 number(s): "50"

Test #8:

score: 0

Accepted

time: 4ms

memory: 67556kb

input:

output:

result:

ok 1 number(s): "41"

Test #9:

score: 0

Accepted

time: 12ms

memory: 67592kb

input:

output:

result:

ok 1 number(s): "49"

Test #10:

score: 0

Accepted

time: 12ms

memory: 67476kb

input:

output:

result:

ok 1 number(s): "47"

Test #11:

score: 0

Accepted

time: 8ms

memory: 67624kb

input:

output:

result:

ok 1 number(s): "49"

Test #12:

score: 0

Accepted

time: 19ms

memory: 67652kb

input:

output:

result:

ok 1 number(s): "897"

Test #13:

score: 0

Accepted

time: 28ms

memory: 67624kb

input:

output:

result:

ok 1 number(s): "1091"

Test #14:

score: 0

Accepted

time: 20ms

memory: 67584kb

input:

output:

result:

ok 1 number(s): "953"

Test #15:

score: 0

Accepted

time: 34ms

memory: 67652kb

input:

output:

result:

ok 1 number(s): "1056"

Test #16:

score: 0

Accepted

time: 32ms

memory: 67652kb

input:

output:

result:

ok 1 number(s): "991"

Test #17:

score: 0

Accepted

time: 8ms

memory: 67596kb

input:

output:

result:

ok 1 number(s): "833"

Test #18:

score: 0

Accepted

time: 19ms

memory: 67512kb

input:

output:

result:

ok 1 number(s): "1028"

Test #19:

score: 0

Accepted

time: 35ms

memory: 67512kb

input:

output:

result:

ok 1 number(s): "1104"

Test #20:

score: 0

Accepted

time: 12ms

memory: 67572kb

input:

output:

result:

ok 1 number(s): "786"

Test #21:

score: 0

Accepted

time: 27ms

memory: 67568kb

input:

output:

result:

ok 1 number(s): "1041"

Test #22:

score: 0

Accepted

time: 19ms

memory: 67540kb

input:

output:

result:

ok 1 number(s): "865"

Test #23:

score: 0

Accepted

time: 24ms

memory: 67508kb

input:

output:

result:

ok 1 number(s): "972"

Test #24:

score: 0

Accepted

time: 25ms

memory: 67572kb

input:

output:

result:

ok 1 number(s): "1107"

Test #25:

score: 0

Accepted

time: 27ms

memory: 67444kb

input:

output:

result:

ok 1 number(s): "1065"

Test #26:

score: 0

Accepted

time: 17ms

memory: 67584kb

input:

output:

result:

ok 1 number(s): "857"

Test #27:

score: 0

Accepted

time: 20ms

memory: 67512kb

input:

output:

result:

ok 1 number(s): "992"

Test #28:

score: 0

Accepted

time: 20ms

memory: 67648kb

input:

output:

result:

ok 1 number(s): "987"

Test #29:

score: 0

Accepted

time: 12ms

memory: 67580kb

input:

output:

result:

ok 1 number(s): "904"

Test #30:

score: 0

Accepted

time: 31ms

memory: 67564kb

input:

output:

result:

ok 1 number(s): "885"

Test #31:

score: 0

Accepted

time: 27ms

memory: 67572kb

input:

output:

result:

ok 1 number(s): "831"

Test #32:

score: 0

Accepted

time: 28ms

memory: 67536kb

input:

output:

result:

ok 1 number(s): "974"

Test #33:

score: 0

Accepted

time: 19ms

memory: 67648kb

input:

output:

result:

ok 1 number(s): "909"

Test #34:

score: 0

Accepted

time: 28ms

memory: 67580kb

input:

output:

result:

ok 1 number(s): "1027"

Test #35:

score: 0

Accepted

time: 29ms

memory: 67536kb

input:

output:

result:

ok 1 number(s): "917"

Test #36:

score: 0

Accepted

time: 12ms

memory: 67580kb

input:

output:

result:

ok 1 number(s): "984"

Test #37:

score: 0

Accepted

time: 16ms

memory: 67572kb

input:

output:

result:

ok 1 number(s): "1055"

Test #38:

score: 0

Accepted

time: 26ms

memory: 67584kb

input:

output:

result:

ok 1 number(s): "982"

Test #39:

score: 0

Accepted

time: 20ms

memory: 67592kb

input:

output:

result:

ok 1 number(s): "904"

Test #40:

score: 0

Accepted

time: 25ms

memory: 67616kb

input:

output:

result:

ok 1 number(s): "882"

Test #41:

score: 0

Accepted

time: 16ms

memory: 67560kb

input:

output:

result:

ok 1 number(s): "823"