QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#422043 | #8276. Code Congestion | ucup-team228# | AC ✓ | 155ms | 5068kb | C++20 | 3.8kb | 2024-05-26 17:13:59 | 2024-05-26 17:13:59 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string to_string(string a) { return '"' + a + '"'; }
string to_string(char a) { return "'" + string(1, a) + "'"; }
string to_string(const char* a) { return to_string((string) a); }
string to_string(bool a) { return a ? "true" : "false"; }
template <class T1, class T2>
string to_string(pair<T1, T2> a) {
return "(" + to_string(a.first) + ", " + to_string(a.second) + ")";
}
template <class T>
string to_string(T a) {
bool first = true; string res = "{";
for (const auto& i : a) {
if (!first) res += ", ";
first = false;
res += to_string(i);
}
res += "}";
return res;
}
void debug_out() { cerr << endl; }
template <class T1, class... T2>
void debug_out(T1 a, T2... b) {
cerr << " " << to_string(a);
debug_out(b...);
}
#ifdef LOCAL
#define out(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define out(...) 42
#endif
clock_t start_time; void start_timer() { start_time = clock(); }
double get_time() { return (double) (clock() - start_time) / CLOCKS_PER_SEC; }
void Solve();
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
freopen("../input.txt", "r", stdin);
#endif
start_timer();
Solve();
#ifdef LOCAL
cerr << fixed << setprecision(3);
cerr << endl << "Time spent: " << get_time() << endl;
#endif
return 0;
}
template <int m>
struct mint {
int x = 0;
mint(int a = 0) : x(a) {}
friend istream& operator>>(istream& is, mint& a) { return is >> a.x; }
friend ostream& operator<<(ostream& os, mint& a) { return os << a.x; }
friend mint binpow(mint a, ll b) {
mint res = 1;
while (b) {
if (b & 1) res *= a;
a *= a;
b >>= 1;
}
return res;
}
mint pow(ll a) const { return binpow(*this, a); }
mint inv() const { return pow(m - 2); }
mint operator-() const { return x ? m - x : 0; }
mint& operator+=(const mint& a) { x += a.x; if (x >= m) x -= m; return *this; }
mint& operator-=(const mint& a) { x -= a.x; if (x < 0) x += m; return *this; }
mint& operator*=(const mint& a) { x = x * 1ll * a.x % m; return *this; }
mint& operator/=(const mint& a) { return *this *= a.inv(); }
friend mint operator+(mint a, const mint& b) { return a += b; }
friend mint operator-(mint a, const mint& b) { return a -= b; }
friend mint operator*(mint a, const mint& b) { return a *= b; }
friend mint operator/(mint a, const mint& b) { return a /= b; }
bool operator==(const mint& a) const { return x == a.x; }
bool operator!=(const mint& a) const { return x != a.x; }
};
const int mod = 998244353;
#define mi mint<mod>
const int N = 205;
const int K = 3e5 + 5;
int a[N];
int t[N];
int pref_t[N];
mi dp[K];
void Solve() {
int n, T;
cin >> n >> T;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
cin >> t[i];
pref_t[i] = min(K, pref_t[i - 1] + t[i]);
}
mi ans = 0;
dp[0] = 1;
for (int i = 1; i <= n; i++) {
mi pref = 0;
for (int j = 0; j <= T - t[i]; j++) {
pref += dp[j];
}
ans += mi(a[i]) * pref * mi(2).pow(n - i);
for (int j = K - t[i]; j >= 0; j--) {
dp[j + t[i]] += dp[j];
}
}
for (int i = 0; i < K; i++) {
dp[i] = 0;
}
dp[0] = 1;
for (int i = n; i >= 1; i--) {
mi suf = 0;
for (int j = 0; j <= T - pref_t[i]; j++) {
suf += dp[j];
}
ans += mi(a[i]) * suf * mi(2).pow(i - 1);
for (int j = K - t[i]; j >= 0; j--) {
dp[j + t[i]] += dp[j];
}
}
cout << ans << "\n";
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 4856kb
input:
3 3 2 3 4 1 2 2
output:
40
result:
ok 1 number(s): "40"
Test #2:
score: 0
Accepted
time: 6ms
memory: 5068kb
input:
13 96 56231 258305 150103 164646 232643 37457 239584 192517 167805 215281 159832 98020 141006 54 1 38 1 4 1 4 11 1 4 8 22 1
output:
745634757
result:
ok 1 number(s): "745634757"
Test #3:
score: 0
Accepted
time: 6ms
memory: 4724kb
input:
14 86 205026 38691 58462 59767 205360 152715 7879 105238 33507 280429 54906 248241 102327 202931 1 49 1 1 5 12 1 5 9 18 1 1 3 32
output:
310231569
result:
ok 1 number(s): "310231569"
Test #4:
score: 0
Accepted
time: 6ms
memory: 4788kb
input:
14 85 82111 267744 229782 32542 260127 152775 1364 293699 23965 242667 264864 219673 189482 12945 1 5 1 1 2 1 38 14 1 3 4 1 21 53
output:
745175834
result:
ok 1 number(s): "745175834"
Test #5:
score: 0
Accepted
time: 6ms
memory: 4836kb
input:
15 94 119505 80865 95965 30047 68261 120903 113180 192738 220899 279742 32609 275645 38640 213859 282516 1 1 8 15 1 3 1 38 6 1 23 57 1 5 79
output:
970187257
result:
ok 1 number(s): "970187257"
Test #6:
score: 0
Accepted
time: 75ms
memory: 4852kb
input:
200 91 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
602403195
result:
ok 1 number(s): "602403195"
Test #7:
score: 0
Accepted
time: 70ms
memory: 4768kb
input:
198 87 276373 259622 211541 127475 41483 45243 254828 92569 120672 280027 180073 248960 25052 110553 136460 102137 166179 165627 29260 33966 121236 34304 67399 250912 104260 114026 261774 159285 218100 110269 112808 224799 170009 150816 34232 290942 52872 176861 177679 36123 92008 39070 265659 25497...
output:
605480487
result:
ok 1 number(s): "605480487"
Test #8:
score: 0
Accepted
time: 155ms
memory: 4828kb
input:
198 234111 89712 73706 49851 196942 284937 252036 155683 1073 160017 24302 1736 21240 97245 116054 17583 258181 102901 54151 14410 251885 121370 135369 278761 195054 259593 292654 222660 193579 111738 119045 14083 214343 1531 298888 25144 88309 170939 62023 113276 169190 31076 65869 121858 158901 89...
output:
762578553
result:
ok 1 number(s): "762578553"
Test #9:
score: 0
Accepted
time: 92ms
memory: 4844kb
input:
199 51347 252659 63409 123416 60355 62358 56763 102379 176682 253785 179538 143669 238937 231314 96387 139004 89373 209360 270990 68703 136192 170160 114701 195611 137800 276330 225931 31636 164292 96730 265083 87466 101920 73722 215904 173793 12439 232863 199992 275055 35058 9090 19991 123969 16126...
output:
659774754
result:
ok 1 number(s): "659774754"
Test #10:
score: 0
Accepted
time: 75ms
memory: 5020kb
input:
199 193 281877 145142 61339 263979 290074 224117 116554 210487 236596 40332 279512 115797 80772 223156 234272 60309 65454 73398 68607 299733 212619 20774 93980 162827 88415 171874 237360 59866 1416 207446 222389 297320 133327 249794 74555 242580 176240 11249 259432 236537 235023 133620 223225 253266...
output:
777218291
result:
ok 1 number(s): "777218291"
Test #11:
score: 0
Accepted
time: 19ms
memory: 4896kb
input:
50 756 228896 201117 28445 23898 258744 221760 287052 284205 213698 193923 238353 273554 104230 45657 48068 142569 97940 136005 101800 70392 236209 269803 277695 4204 265615 186800 177441 269603 91437 121026 138283 187248 1793 144329 49812 214068 82633 271800 238111 206107 133808 131678 242602 12854...
output:
306757123
result:
ok 1 number(s): "306757123"
Test #12:
score: 0
Accepted
time: 19ms
memory: 5024kb
input:
49 896 222309 2984 141214 27320 70356 118537 243187 22055 16410 153276 110109 130296 100243 177715 278896 101771 175797 56180 43194 61709 83723 97026 66548 59377 290607 160007 243770 83478 162572 130113 295614 209317 270726 8240 217891 152168 149444 5953 150962 263112 251413 76008 262290 143396 9526...
output:
233615829
result:
ok 1 number(s): "233615829"
Test #13:
score: 0
Accepted
time: 19ms
memory: 4768kb
input:
50 825 22363 122426 144773 97133 182022 18905 64350 203411 57289 271378 115220 232152 146084 266835 71723 126783 140286 235142 161866 128092 4130 101780 26989 260105 223801 30789 204088 214173 30402 26543 11257 10749 45731 22534 152504 183529 117907 267801 293541 64520 46809 108156 9737 85517 51204 ...
output:
681195538
result:
ok 1 number(s): "681195538"
Test #14:
score: 0
Accepted
time: 38ms
memory: 5068kb
input:
98 8721 263042 289529 281955 89427 133885 50755 31062 103483 238269 127989 20094 247724 279099 181766 23924 80919 195591 295595 40269 71727 265824 170041 263460 68994 4726 179354 9077 116845 189303 44780 74054 155808 212015 91437 111256 209026 206198 44791 253213 163971 211258 144041 90842 205519 89...
output:
200292113
result:
ok 1 number(s): "200292113"
Test #15:
score: 0
Accepted
time: 37ms
memory: 4832kb
input:
98 8741 225872 288700 189511 196806 225120 274217 253157 146444 287797 3621 285106 38854 108280 188488 142516 160737 273780 129763 163930 201755 56670 119433 191038 73304 34842 202380 86150 173214 91738 293005 106191 56375 2859 83899 26631 18876 264951 41688 242722 124753 201474 112811 86496 215052 ...
output:
459746433
result:
ok 1 number(s): "459746433"
Test #16:
score: 0
Accepted
time: 141ms
memory: 4864kb
input:
199 277574 141689 225272 125107 151768 228208 186804 175264 16827 295516 209526 124641 261221 82656 270676 133451 143319 88685 240621 34249 278052 4419 78260 133343 92452 50129 49693 236168 166685 129020 32845 272172 230472 204327 48649 284108 275518 204892 54401 280521 115533 132840 270666 189150 8...
output:
240734076
result:
ok 1 number(s): "240734076"
Test #17:
score: 0
Accepted
time: 148ms
memory: 4900kb
input:
198 287619 284916 203413 139843 49889 185866 266946 266531 17129 197121 293732 257581 219723 150578 205283 6917 72781 23158 250507 204911 159775 293674 101678 191008 197221 76481 285483 164212 84643 288481 97161 273155 73778 182788 158493 175712 291729 109425 242114 18948 3201 119804 58576 35651 129...
output:
126120693
result:
ok 1 number(s): "126120693"
Test #18:
score: 0
Accepted
time: 77ms
memory: 5064kb
input:
200 6612 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
929053212
result:
ok 1 number(s): "929053212"
Test #19:
score: 0
Accepted
time: 74ms
memory: 4816kb
input:
199 84 243795 165034 5639 75935 238817 147929 226544 293534 240274 90288 252102 106448 113215 48270 194928 286677 82268 16947 230906 291653 199441 196874 79425 231429 152205 180248 119488 20333 288621 26675 282256 286762 167295 262598 281773 199863 12706 83475 253214 169666 220315 33554 67239 299655...
output:
575921893
result:
ok 1 number(s): "575921893"
Test #20:
score: 0
Accepted
time: 19ms
memory: 4764kb
input:
49 803 288550 178987 294656 45204 282141 282775 68955 162258 75410 110866 154922 81774 138136 225479 205313 201679 104440 180675 9993 27446 44142 126909 124465 283498 156316 140718 150698 11003 227369 285704 208605 118444 42585 180580 163296 105493 171367 58057 270297 171145 186544 188305 161117 198...
output:
571469511
result:
ok 1 number(s): "571469511"
Test #21:
score: 0
Accepted
time: 131ms
memory: 4900kb
input:
198 258829 72869 103820 171732 88624 103832 207683 215248 129683 13606 59143 163386 286685 233726 60517 221204 70924 54072 271213 150284 80276 183493 123387 166471 244404 42566 278360 89026 150459 169611 218017 160379 220794 45830 112855 144288 149952 141077 205393 139375 114955 116736 279440 210708...
output:
32373803
result:
ok 1 number(s): "32373803"
Extra Test:
score: 0
Extra Test Passed