# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1259716 | phtung | Topical (NOI23_topical) | C++20 | 299 ms | 126500 KiB |
#include <bits/stdc++.h>
using namespace std;
#define name "IO"
#define int long long
const int inf = 1e18 + 7;
const int maxn = 1e6 + 5;
int n, k;
vector<vector<int>> r, u;
void sub1()
{
for(int j = 1; j <= k; j++)
{
if(r[1][j] > 0)
{
cout << 0 << "\n";
return;
}
}
cout << 1 << "\n";
}
void sub3()
{
vector<pair<int,int>> a;
for(int i = 1; i <= n; i++)
{
a.push_back({r[i][1], u[i][1]});
}
sort(a.begin(), a.end());
int cur = 0, res = 0;
for(auto [val, add] : a)
{
if(cur >= val)
{
cur += add;
res++;
}
}
cout << res << "\n";
}
void sub2()
{
int res = 0;
vector<int> cur(k + 1, 0), vis(n + 1, 0);
while(true)
{
int cnt = 0;
for(int i = 1; i <= n; i++)
{
if(vis[i]) continue;
bool ok = 1;
for(int j = 1; j <= k; j++)
{
if(cur[j] < r[i][j])
{
ok = 0;
break;
}
}
if(ok)
{
cnt++;
for(int j = 1; j <= k; j++) cur[j] += u[i][j];
vis[i] = 1;
}
}
if(!cnt) break;
res += cnt;
}
cout << res << "\n";
}
void solve()
{
cin >> n >> k;
r.resize(n + 1, vector<int>(k + 1)), u.resize(n + 1, vector<int>(k + 1));
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= k; j++)
{
cin >> r[i][j];
}
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= k; j++)
{
cin >> u[i][j];
}
}
if(n == 1) sub1();
else if(k == 1) sub3();
else if(n <= 100) sub2();
}
signed main()
{
if (fopen (name".INP", "r"))
{
freopen (name".INP", "r", stdin);
freopen (name".OUT", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
clock_t start = clock();
int t = 1;
while(t--) solve();
std::cerr << "Time: " << clock() - start << "ms\n";
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |