제출 #580483

#제출 시각아이디문제언어결과실행 시간메모리
580483talant117408Lottery (CEOI18_lot)C++17
45 / 100
3097 ms736 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair <int, int> pii; typedef pair <ll, ll> pll; #define long unsigned long #define pb push_back #define mp make_pair #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define lb lower_bound #define ub upper_bound #define sz(v) int((v).size()) #define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define endl '\n' void solve() { int n, l; cin >> n >> l; vector <int> v(n); for (auto &to : v) cin >> to; int q; cin >> q; vector <pii> queries(q); for (int i = 0; i < q; i++) { cin >> queries[i].first; queries[i].second = i; } sort(all(queries)); vector <vector <int>> dp(q+1, vector <int> (n)); for (int i = 0; i < n-l+1; i++) { for (int j = i+1; j < n-l+1; j++) { int cnt = 0; for (int k = 0; k < l; k++) cnt += (v[i+k] != v[j+k]); auto it = lb(all(queries), mp(cnt, 0))-queries.begin(); dp[it][i]++; dp[it][j]++; } } vector <vector <int>> ans(q, vector <int> (n)); for (int i = 0; i < n-l+1; i++) for (int j = 1; j < q; j++) { dp[j][i] += dp[j-1][i]; } for (int j = 0; j < q; j++) { ans[queries[j].second] = dp[j]; } for (int j = 0; j < q; j++) { for (int i = 0; i < n-l+1; i++) { cout << ans[j][i] << ' '; } cout << endl; } } int main() { do_not_disturb int t = 1; //~ cin >> t; while (t--) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...