# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
132639 | SamAnd | Lottery (CEOI18_lot) | C++17 | 165 ms | 47864 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N = 2003;
int n, m;
int a[N];
vector<int> v[N];
int b[N][N];
void ubd(int x1, int x2, int y1, int y2)
{
b[x1][y1]++;
b[x2 + 1][y2 + 1]--;
}
int p[N][N];
int main()
{
//freopen("input.txt", "r", stdin);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
if (a[i] != a[j])
{
int x1 = i - m + 1;
int x2 = i;
int y1 = j - m + 1;
int y2 = j;
int t1 = 0, t2 = 0;
t1 = max(t1, 1 - x1);
t2 = max(t2, x2 - (n - m + 1));
t1 = max(t1, 1 - y1);
t2 = max(t2, y2 - (n - m + 1));
x1 += t1;
y1 += t1;
x2 -= t2;
y2 -= t2;
ubd(x1, x2, y1, y2);
}
}
}
for (int i = 1; i <= n - m + 1; ++i)
{
for (int j = 1; j <= n - m + 1; ++j)
{
p[i][j] = p[i - 1][j - 1] + b[i][j];
if (i != j)
{
v[i].push_back(p[i][j]);
}
}
}
for (int i = 1; i <= n - m + 1; ++i)
sort(v[i].begin(), v[i].end());
int q;
scanf("%d", &q);
while (q--)
{
int d;
scanf("%d", &d);
for (int i = 1; i <= n - m + 1; ++i)
{
printf("%d ", upper_bound(v[i].begin(), v[i].end(), d) - v[i].begin());
}
printf("\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... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |