QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #46822 | #976. GPA | Ufowoqqqo | AC ✓ | 35ms | 67652kb | C++ | 833b | 2022-09-01 23:31:46 | 2022-09-01 23:31:48 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 67568kb
input:
4 1 2 2 3 1 2 1 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 16ms
memory: 67548kb
input:
140 67 66 259 29 400 292 363 89 355 93 183 141 250 73 81 307 208 14 263 36 310 4 304 177 308 323 136 303 204 4 96 326 134 174 185 179 359 27 145 193 365 266 55 70 281 111 56 235 90 146 344 328 308 254 22 338 238 369 327 177 341 357 43 23 115 296 321 104 373 253 253 276 91 167 213 58 272 59 230 5 350...
output:
31
result:
ok 1 number(s): "31"
Test #3:
score: 0
Accepted
time: 16ms
memory: 67488kb
input:
190 51 297 340 215 184 193 293 248 197 239 230 286 66 360 254 57 31 146 319 18 326 316 177 360 95 201 28 0 153 157 282 271 42 384 332 52 304 148 97 132 274 95 388 399 153 234 280 77 31 280 213 325 168 124 283 369 303 109 235 257 98 151 26 59 95 200 264 299 148 335 251 148 297 316 16 387 169 327 338 ...
output:
44
result:
ok 1 number(s): "44"
Test #4:
score: 0
Accepted
time: 16ms
memory: 67488kb
input:
158 19 155 13 256 95 310 48 251 165 187 216 398 263 31 105 148 99 149 183 308 21 119 348 9 349 132 8 3 224 384 20 158 127 168 210 271 211 165 150 128 386 65 280 91 48 395 131 333 363 119 368 150 107 300 103 60 126 80 234 270 298 393 321 287 267 193 275 178 300 151 75 319 33 60 78 38 228 263 345 365 ...
output:
40
result:
ok 1 number(s): "40"
Test #5:
score: 0
Accepted
time: 11ms
memory: 67516kb
input:
200 41 145 158 196 38 243 8 354 114 167 354 36 67 62 206 55 218 274 176 42 357 181 198 224 394 278 194 62 18 296 90 391 247 299 77 383 148 7 29 298 299 32 136 288 332 322 209 114 193 345 180 159 44 386 366 312 288 88 355 161 360 393 304 220 15 167 151 352 247 149 0 162 149 160 45 349 7 212 143 398 3...
output:
56
result:
ok 1 number(s): "56"
Test #6:
score: 0
Accepted
time: 4ms
memory: 67592kb
input:
192 111 147 337 395 114 30 187 130 243 115 16 145 64 30 384 139 110 160 368 36 56 103 189 317 82 270 143 80 353 14 216 49 206 320 192 43 302 22 300 81 208 55 290 209 100 302 245 72 278 262 383 240 8 121 91 248 324 227 56 82 388 54 269 68 100 220 345 330 319 213 201 357 132 266 375 305 305 41 155 37 ...
output:
50
result:
ok 1 number(s): "50"
Test #7:
score: 0
Accepted
time: 15ms
memory: 67592kb
input:
189 264 11 265 241 258 394 188 126 42 104 246 341 397 215 131 400 35 70 372 16 300 129 87 66 295 188 360 204 21 274 371 323 110 377 327 140 381 296 152 109 319 347 392 176 298 179 297 343 377 180 73 245 314 277 30 239 148 188 95 249 126 372 236 194 226 397 397 112 248 152 348 161 353 5 146 55 385 64...
output:
50
result:
ok 1 number(s): "50"
Test #8:
score: 0
Accepted
time: 4ms
memory: 67556kb
input:
143 123 304 269 215 185 375 157 252 48 264 316 228 173 310 211 101 344 184 89 263 279 205 131 294 249 166 182 53 108 129 383 128 355 284 145 294 184 181 115 81 219 289 371 118 49 310 114 228 13 230 294 163 28 58 160 160 368 14 65 44 318 341 259 194 94 230 64 117 22 134 256 103 191 286 254 130 349 14...
output:
41
result:
ok 1 number(s): "41"
Test #9:
score: 0
Accepted
time: 12ms
memory: 67592kb
input:
188 318 297 211 137 85 52 265 184 3 266 261 367 119 134 79 134 22 75 123 328 98 118 233 343 362 337 28 357 135 49 176 259 113 165 53 58 156 165 358 81 136 377 126 363 219 308 79 248 238 112 178 23 169 247 156 220 396 67 311 98 191 146 305 134 271 318 194 168 97 279 312 174 283 220 289 386 196 293 10...
output:
49
result:
ok 1 number(s): "49"
Test #10:
score: 0
Accepted
time: 12ms
memory: 67476kb
input:
180 35 157 351 189 330 0 72 390 126 353 315 345 156 6 373 150 148 319 276 104 305 153 298 249 253 198 98 65 73 298 29 202 108 43 348 15 187 29 118 112 289 315 133 212 252 280 6 186 280 91 169 237 84 23 184 82 302 254 110 123 224 387 48 312 393 291 31 310 115 175 50 260 340 314 160 79 2 254 9 375 58 ...
output:
47
result:
ok 1 number(s): "47"
Test #11:
score: 0
Accepted
time: 8ms
memory: 67624kb
input:
157 382 381 24 92 266 390 240 59 96 8 198 114 177 271 132 150 331 390 382 137 296 276 312 347 45 169 146 24 394 305 291 228 103 255 341 373 55 84 37 213 155 43 232 23 328 373 294 297 182 174 343 28 210 93 199 68 337 92 56 88 179 44 278 103 82 234 284 4 185 29 208 323 207 33 16 194 286 348 75 280 363...
output:
49
result:
ok 1 number(s): "49"
Test #12:
score: 0
Accepted
time: 19ms
memory: 67652kb
input:
3117 398 0 26 48 89 256 145 73 217 22 349 43 342 153 302 213 221 318 42 200 373 51 276 230 65 372 120 156 61 295 3 371 124 173 189 41 364 221 298 387 394 231 384 83 0 82 398 226 347 385 118 287 101 0 102 369 104 257 40 75 386 243 350 179 262 199 173 13 159 215 17 213 376 125 358 120 118 370 44 333 1...
output:
897
result:
ok 1 number(s): "897"
Test #13:
score: 0
Accepted
time: 28ms
memory: 67624kb
input:
3881 109 367 140 272 6 206 79 203 49 174 191 274 149 85 162 2 394 67 397 23 223 288 237 383 133 70 180 42 108 82 341 182 115 155 169 322 70 49 59 318 274 245 144 351 291 281 36 199 100 86 159 22 22 55 1 12 190 90 248 291 152 107 141 317 177 267 297 352 103 61 18 241 270 180 271 311 115 209 270 307 3...
output:
1091
result:
ok 1 number(s): "1091"
Test #14:
score: 0
Accepted
time: 20ms
memory: 67584kb
input:
3351 333 222 152 209 389 198 194 154 171 252 230 353 234 73 200 53 212 363 304 339 242 265 61 131 147 69 9 281 360 206 213 273 100 258 150 296 234 284 284 289 87 8 358 1 389 284 294 259 132 188 266 157 376 189 175 152 167 247 298 195 171 326 85 336 123 383 348 127 315 154 87 223 113 58 109 386 153 1...
output:
953
result:
ok 1 number(s): "953"
Test #15:
score: 0
Accepted
time: 34ms
memory: 67652kb
input:
3695 95 199 272 94 114 341 335 343 329 369 144 278 28 58 136 138 294 329 52 22 320 43 247 299 118 323 186 64 296 100 370 17 31 399 313 392 202 29 393 288 216 164 341 33 200 6 184 125 62 335 248 206 264 145 169 307 364 32 78 393 156 17 165 29 9 205 105 282 242 283 120 47 65 98 78 246 43 79 6 291 17 1...
output:
1056
result:
ok 1 number(s): "1056"
Test #16:
score: 0
Accepted
time: 32ms
memory: 67652kb
input:
3518 315 241 321 19 42 139 369 188 166 172 47 190 329 273 321 50 385 334 276 274 11 215 65 72 285 24 174 150 97 29 197 96 142 194 359 336 241 172 28 153 370 378 71 167 15 392 155 324 17 68 278 222 13 220 285 119 348 163 332 300 4 72 311 370 64 203 189 244 98 71 89 39 208 80 267 296 358 386 93 351 11...
output:
991
result:
ok 1 number(s): "991"
Test #17:
score: 0
Accepted
time: 8ms
memory: 67596kb
input:
2882 346 374 192 216 31 374 397 382 221 17 315 379 353 118 157 391 37 313 93 31 230 200 264 181 171 8 258 151 54 9 203 291 152 120 184 170 356 143 59 57 274 285 257 6 191 192 200 150 240 305 93 337 229 22 292 345 264 348 84 290 227 295 216 263 151 59 382 202 173 18 79 162 324 224 186 390 353 277 357...
output:
833
result:
ok 1 number(s): "833"
Test #18:
score: 0
Accepted
time: 19ms
memory: 67512kb
input:
3695 280 16 131 54 150 26 82 96 364 150 73 175 369 339 69 60 168 370 137 199 20 54 157 319 321 242 135 267 204 395 306 235 238 40 336 15 331 251 341 286 335 255 144 234 19 239 343 258 388 68 4 32 34 78 201 79 363 193 183 313 355 349 105 251 339 179 45 261 24 102 255 89 265 372 47 197 313 218 160 374...
output:
1028
result:
ok 1 number(s): "1028"
Test #19:
score: 0
Accepted
time: 35ms
memory: 67512kb
input:
3903 193 40 159 400 364 88 235 320 61 201 218 249 171 12 63 66 249 118 228 27 388 9 352 300 152 188 33 289 245 147 4 284 278 197 200 360 305 381 348 230 259 261 162 342 219 115 178 237 326 199 376 133 260 30 271 84 184 45 69 17 276 229 262 305 178 36 245 214 321 268 22 370 183 135 34 296 377 27 39 1...
output:
1104
result:
ok 1 number(s): "1104"
Test #20:
score: 0
Accepted
time: 12ms
memory: 67572kb
input:
2832 19 80 272 83 199 374 18 277 74 278 121 190 209 141 147 337 116 164 230 159 40 386 87 221 354 366 114 102 16 339 101 133 341 204 258 60 161 8 349 366 178 34 314 86 87 375 126 373 372 270 209 328 369 383 360 108 254 361 68 272 180 301 333 327 379 178 360 88 186 139 189 231 352 216 315 282 197 158...
output:
786
result:
ok 1 number(s): "786"
Test #21:
score: 0
Accepted
time: 27ms
memory: 67568kb
input:
3760 334 161 333 373 101 359 16 28 41 110 62 199 375 271 103 350 120 310 12 84 294 204 324 168 324 43 312 193 269 212 55 180 29 21 299 101 243 69 94 318 6 129 264 142 223 64 36 43 383 199 25 359 95 57 115 302 242 370 90 400 208 325 117 22 309 4 395 322 383 208 71 300 389 40 379 318 398 241 339 209 1...
output:
1041
result:
ok 1 number(s): "1041"
Test #22:
score: 0
Accepted
time: 19ms
memory: 67540kb
input:
3121 230 171 392 317 270 103 397 211 247 68 148 3 146 279 193 328 2 227 383 307 325 330 244 366 259 38 68 256 41 22 123 14 4 380 9 120 120 301 129 289 248 232 282 66 344 230 206 186 174 222 214 149 286 309 228 245 325 255 398 152 174 36 191 43 69 204 269 187 340 23 192 197 82 12 328 311 123 218 52 3...
output:
865
result:
ok 1 number(s): "865"
Test #23:
score: 0
Accepted
time: 24ms
memory: 67508kb
input:
3491 311 23 292 68 295 8 186 89 139 268 174 357 26 173 397 339 116 274 181 54 144 316 377 8 79 167 25 74 237 40 51 80 332 20 381 316 133 52 271 90 294 353 199 207 325 228 217 49 195 350 329 178 279 77 310 373 58 217 176 270 160 318 277 384 348 91 151 270 253 39 259 58 331 249 323 184 213 329 298 85 ...
output:
972
result:
ok 1 number(s): "972"
Test #24:
score: 0
Accepted
time: 25ms
memory: 67572kb
input:
3995 159 371 294 41 277 250 152 45 296 161 26 205 385 102 130 104 41 125 26 2 318 204 211 21 153 369 386 65 276 166 122 76 48 199 349 1 356 40 372 152 330 137 84 31 33 325 269 296 268 43 90 268 42 122 394 245 319 389 98 88 15 293 15 206 88 0 100 368 374 265 294 321 279 368 267 71 69 127 340 390 283 ...
output:
1107
result:
ok 1 number(s): "1107"
Test #25:
score: 0
Accepted
time: 27ms
memory: 67444kb
input:
3924 279 1 276 275 232 239 88 349 309 116 383 260 358 23 168 100 247 360 214 99 345 211 397 77 365 76 176 341 343 197 32 210 389 345 44 318 361 43 256 265 4 160 242 313 143 224 130 250 74 142 172 176 71 368 180 221 209 205 158 319 143 7 139 322 24 4 156 258 192 149 18 392 337 49 228 216 133 281 240 ...
output:
1065
result:
ok 1 number(s): "1065"
Test #26:
score: 0
Accepted
time: 17ms
memory: 67584kb
input:
3065 378 171 177 183 287 384 284 204 147 306 342 202 297 262 166 97 219 366 309 43 383 61 254 247 227 51 174 157 124 194 166 378 42 228 360 181 353 4 75 76 68 398 399 331 395 364 388 121 118 339 95 260 53 284 149 196 132 105 378 58 127 260 320 0 173 109 146 302 353 166 298 183 217 382 60 104 144 366...
output:
857
result:
ok 1 number(s): "857"
Test #27:
score: 0
Accepted
time: 20ms
memory: 67512kb
input:
3379 237 112 291 80 383 172 276 231 89 353 371 5 308 366 342 185 227 379 45 11 62 21 331 134 1 144 393 346 104 119 51 196 218 397 384 187 135 142 34 341 233 258 353 156 143 81 76 375 48 160 158 140 337 162 277 217 119 165 111 365 216 348 16 92 357 332 74 252 240 129 99 290 315 56 267 166 254 358 203...
output:
992
result:
ok 1 number(s): "992"
Test #28:
score: 0
Accepted
time: 20ms
memory: 67648kb
input:
3544 266 118 381 38 381 149 193 371 203 318 374 186 223 103 64 354 69 308 64 163 242 62 47 124 397 138 265 235 100 168 52 225 368 2 80 238 223 372 208 172 8 256 322 209 366 142 190 63 25 109 287 281 337 396 108 226 198 396 364 254 142 6 185 219 90 99 243 295 53 166 305 355 335 94 286 12 127 39 107 3...
output:
987
result:
ok 1 number(s): "987"
Test #29:
score: 0
Accepted
time: 12ms
memory: 67580kb
input:
3222 109 283 83 81 169 387 280 306 335 48 336 244 111 267 273 36 14 111 207 225 73 22 283 15 176 360 79 41 40 62 19 145 283 75 118 369 397 333 349 105 84 266 79 44 65 119 298 129 369 19 62 102 173 368 164 281 191 335 372 31 178 244 305 292 397 185 39 103 286 192 224 399 354 342 21 59 211 154 354 389...
output:
904
result:
ok 1 number(s): "904"
Test #30:
score: 0
Accepted
time: 31ms
memory: 67564kb
input:
3169 98 232 78 76 165 306 246 216 308 68 384 226 257 97 201 213 256 48 347 248 353 4 337 229 58 263 164 323 69 61 280 59 88 83 273 195 55 118 364 249 10 394 308 257 107 78 372 219 49 38 297 47 42 47 295 157 339 168 18 90 56 348 321 373 323 112 351 64 144 137 33 268 384 168 216 392 171 122 176 220 32...
output:
885
result:
ok 1 number(s): "885"
Test #31:
score: 0
Accepted
time: 27ms
memory: 67572kb
input:
2981 169 351 232 128 177 286 166 358 69 306 374 63 366 365 100 373 250 257 355 236 276 38 129 50 298 43 225 232 125 167 271 306 182 349 195 108 361 266 62 18 306 392 317 60 215 10 101 336 296 321 18 63 114 232 280 168 321 378 286 279 46 117 303 381 344 145 266 133 326 20 12 15 193 399 90 246 212 71 ...
output:
831
result:
ok 1 number(s): "831"
Test #32:
score: 0
Accepted
time: 28ms
memory: 67536kb
input:
3452 324 128 219 343 119 316 126 52 264 195 107 263 272 19 316 212 223 308 345 305 68 302 317 242 277 65 361 305 134 277 228 370 335 70 281 311 388 149 276 113 110 303 108 151 54 354 195 179 12 159 369 281 282 209 357 189 18 115 169 112 72 231 228 96 203 195 244 238 94 380 171 215 294 374 236 27 245...
output:
974
result:
ok 1 number(s): "974"
Test #33:
score: 0
Accepted
time: 19ms
memory: 67648kb
input:
3267 342 152 24 196 111 87 70 112 378 74 148 76 314 166 165 308 213 26 264 221 231 36 329 252 174 267 373 348 89 384 229 324 13 57 31 358 156 112 298 296 220 383 134 8 287 145 33 13 203 29 45 145 148 99 44 263 399 248 216 200 86 22 45 92 270 63 121 130 305 357 169 122 60 100 305 170 14 153 25 158 21...
output:
909
result:
ok 1 number(s): "909"
Test #34:
score: 0
Accepted
time: 28ms
memory: 67580kb
input:
3611 248 268 21 118 323 10 100 96 161 44 168 76 74 155 149 252 269 138 170 248 57 205 333 316 397 207 385 266 257 349 33 250 85 261 5 81 160 311 75 394 321 342 290 272 244 196 343 29 221 182 261 339 302 30 115 23 202 140 132 69 112 400 5 104 245 81 81 48 144 150 104 3 264 165 338 270 142 260 299 213...
output:
1027
result:
ok 1 number(s): "1027"
Test #35:
score: 0
Accepted
time: 29ms
memory: 67536kb
input:
3244 95 248 126 303 301 190 7 32 171 250 160 115 253 111 234 22 396 45 15 38 227 355 154 319 68 54 8 123 184 113 146 129 161 174 229 20 223 85 281 17 353 382 43 176 92 67 0 235 105 206 47 178 283 254 400 0 180 229 67 122 288 344 144 21 360 101 49 60 387 92 288 232 327 304 283 89 106 211 113 349 115 ...
output:
917
result:
ok 1 number(s): "917"
Test #36:
score: 0
Accepted
time: 12ms
memory: 67580kb
input:
3462 273 130 191 142 206 91 185 291 170 375 373 144 101 164 50 379 289 171 44 72 110 306 307 232 354 124 134 102 227 289 380 343 125 63 120 384 146 104 268 249 67 49 58 166 57 150 92 346 104 288 222 106 94 40 248 328 147 96 30 28 391 59 155 258 150 383 161 264 277 174 168 257 54 138 191 77 72 109 28...
output:
984
result:
ok 1 number(s): "984"
Test #37:
score: 0
Accepted
time: 16ms
memory: 67572kb
input:
3653 297 205 288 21 311 178 364 96 88 146 144 108 91 260 242 0 220 162 229 221 349 46 164 242 263 11 216 75 345 249 318 385 96 115 190 385 267 212 91 193 375 300 191 20 325 218 268 325 183 214 313 96 268 314 103 352 176 327 245 14 318 23 114 187 119 15 127 257 160 388 303 225 242 250 107 349 329 344...
output:
1055
result:
ok 1 number(s): "1055"
Test #38:
score: 0
Accepted
time: 26ms
memory: 67584kb
input:
3456 247 314 15 322 150 169 286 295 275 216 51 131 67 298 198 87 51 319 197 141 166 127 311 376 146 98 257 150 257 197 165 397 83 224 393 190 163 317 343 44 320 364 316 375 178 35 54 125 331 16 185 320 302 338 318 344 15 42 187 143 83 121 194 353 285 230 274 169 49 248 87 51 54 197 0 394 271 287 110...
output:
982
result:
ok 1 number(s): "982"
Test #39:
score: 0
Accepted
time: 20ms
memory: 67592kb
input:
3301 295 249 15 363 377 168 391 97 369 21 42 76 143 67 140 70 224 254 4 30 267 124 372 256 114 169 64 230 205 116 119 170 84 337 296 300 158 301 336 74 255 220 220 65 85 186 71 303 389 178 339 189 148 6 335 115 115 232 160 395 385 251 235 214 182 398 233 385 326 33 383 224 393 235 118 394 381 23 212...
output:
904
result:
ok 1 number(s): "904"
Test #40:
score: 0
Accepted
time: 25ms
memory: 67616kb
input:
3147 140 103 25 398 119 283 44 186 174 322 135 29 325 360 82 296 321 6 31 86 392 59 222 58 261 119 280 275 52 99 75 26 190 223 15 112 35 278 335 89 354 375 61 19 157 305 254 315 250 135 298 61 247 303 258 395 230 272 306 306 315 385 115 165 175 157 333 372 171 39 162 257 56 278 177 269 113 292 231 1...
output:
882
result:
ok 1 number(s): "882"
Test #41:
score: 0
Accepted
time: 16ms
memory: 67560kb
input:
2897 180 264 265 64 146 15 37 121 36 237 346 396 212 304 232 263 343 326 200 244 238 386 348 268 1 328 196 193 288 303 161 388 368 176 343 156 205 154 64 109 166 127 219 18 69 120 196 100 369 344 341 387 343 20 270 323 268 319 128 385 325 186 208 134 166 11 87 102 72 80 143 329 289 47 152 35 116 390...
output:
823
result:
ok 1 number(s): "823"