A - Airport Bus
A - Airport Bus
#include <bits/stdc++.h> #define rep(i,n) for(int i=0; i<(n); ++i) #define repx(i,x,n) for(int i=x; i<(n); ++i) #define fixed_setprecision(n) fixed << setprecision((n)) #define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC); #define pai 3.1415926535897932384 #define NUM_MAX 2e18 #define NUM_MIN -1e9 using namespace std; using ll = long long; using P = pair<int,int>; template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; } int main(){ int N, C, K; cin >> N >> C >> K; vector<int> A(N); for(auto &a:A) cin >> a; sort(A.begin(), A.end()); vector<int> v; int cnt=0; for(int i=0; i<N; i++){ int ok=1; if(v.size() > 0 && v[0] + K < A[i]){ ok = 0; } if(v.size()>=C || ok == 0){ v.erase(v.begin(), v.end()); cnt++; } v.push_back(A[i]); } if(v.size()) cnt++; cout << cnt << endl; return 0; }
C - Traveling Plan
C - Traveling Plan
O(N)
#include <bits/stdc++.h> #define rep(i,n) for(int i=0; i<(n); ++i) #define repx(i,x,n) for(int i=x; i<(n); ++i) #define fixed_setprecision(n) fixed << setprecision((n)) #define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC); #define pai 3.1415926535897932384 #define NUM_MAX 2e18 #define NUM_MIN -1e9 using namespace std; using ll = long long; using P = pair<int,int>; template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; } int main(){ int N; cin >> N; vector<int> A(N); for(auto &a:A) cin >> a; int sum=0; for(int i=0; i<N; i++){ int pos=0; if(i) pos = A[i-1]; sum += abs(A[i] - pos); } sum += abs(0 - A[N-1]); for(int i=0; i<N; i++){ int pos=0; int t = sum; if(i) pos = A[i-1]; if(i<N-1){ t -= abs(A[i] - pos); t -= abs(A[i+1] - A[i]); t += abs(A[i+1] - pos); }else{ t -= abs(0 - A[i]); t -= abs(A[i] - A[i-1]); t += abs(0 - A[i-1]); } cout << t << endl; } return 0; }
C - Streamline
C - Streamline
#include <bits/stdc++.h> #define rep(i,n) for(int i=0; i<(n); ++i) #define repx(i,x,n) for(int i=x; i<(n); ++i) #define fixed_setprecision(n) fixed << setprecision((n)) #define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC); #define pai 3.1415926535897932384 #define NUM_MAX 2e18 #define NUM_MIN -1e9 using namespace std; using ll = long long; using P = pair<int,int>; template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; } int main() { int N, M; cin >> N >> M; vector<int> X(M); for(auto &x:X) cin >> x; sort(X.begin(), X.end()); vector<int> d(M-1); for(int i=0; i<M-1; i++) d[i] = X[i+1] - X[i]; sort(d.begin(), d.end()); int ans=0; for(int i=0; i<M-N; i++) ans+=d[i]; cout << ans << endl; return 0; }
C - When I hit my pocket...
C - When I hit my pocket...
#include <bits/stdc++.h> #define rep(i,n) for(int i=0; i<(n); ++i) #define repx(i,x,n) for(int i=x; i<(n); ++i) #define fixed_setprecision(n) fixed << setprecision((n)) #define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC); #define pai 3.1415926535897932384 #define NUM_MAX 2e18 #define NUM_MIN -1e9 using namespace std; using ll = long long; using P = pair<int,int>; template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; } int main() { ll K, A, B; cin >> K >> A >> B; if(B-A>=2){ ll d = min(K, A-1); ll ans = d + 1; K -= d; ans += K / 2 * (B - A); ans += K % 2; cout << ans << endl; }else{ cout << K + 1 << endl; } return 0; }
C - Skip
C - Skip
#include <bits/stdc++.h> #define rep(i,n) for(int i=0; i<(n); ++i) #define repx(i,x,n) for(int i=x; i<(n); ++i) #define fixed_setprecision(n) fixed << setprecision((n)) #define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC); #define pai 3.1415926535897932384 #define NUM_MAX 2e18 #define NUM_MIN -1e9 using namespace std; using ll = long long; using P = pair<int,int>; template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; } /* name: gcd proc: ユークリッドの互除法 */ int gcd(int x, int y){ if(x<y) swap(x, y); while(y>0){ int r = x % y; x = y; y = r; } return x; } int main() { int N, X; cin >> N >> X; vector<int> A(N); for(auto &a:A) cin >> a; vector<int> d(N); for(int i=0; i<N; i++){ d[i] = abs(A[i] - X); } if(N==1){ cout << d[0] << endl; }else{ int ans = gcd(d[0], d[1]); for(int i=2; i<N; i++){ ans = gcd(d[i], ans); } cout << ans << endl; } return 0; }
C - Minimization
C - Minimization
O(1)
#include <bits/stdc++.h> #define rep(i,n) for(int i=0; i<(n); ++i) #define repx(i,x,n) for(int i=x; i<(n); ++i) #define fixed_setprecision(n) fixed << setprecision((n)) #define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC); #define pai 3.1415926535897932384 #define NUM_MAX 2e18 #define NUM_MIN -1e9 using namespace std; using ll = long long; using P = pair<int,int>; template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; } int main() { int N, K; cin >> N >> K; vector<int> A(N); for(auto &a:A) cin >> a; cout << (N -1 + K - 2) / (K-1) << endl; return 0; }
B - Two Anagram
B - Two Anagrams
#include <bits/stdc++.h> #define rep(i,n) for(int i=0; i<(n); ++i) #define repx(i,x,n) for(int i=x; i<(n); ++i) #define fixed_setprecision(n) fixed << setprecision((n)) #define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC); #define pai 3.1415926535897932384 #define NUM_MAX 2e18 #define NUM_MIN -1e9 using namespace std; using ll = long long; using P = pair<int,int>; template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; } int main() { string s, t; cin >> s >> t; sort(s.begin(), s.end()); sort(t.begin(), t.end(), [](const auto& x, const auto& y){ return x>y; }); if(s < t) cout << "Yes" << endl; else cout << "No" << endl; return 0; }