akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

#define MOD 1000000007
#define MOD2 998244353
#define int long long
#define double long double
#define EPS 1e-9
//#define PI 3.14159265358979

#define rep(i, n) for (int i = 0; i < (int)(n); i++)

using namespace std;

template < typename T >
ostream &operator<<(ostream &os, const vector< T > &A) {
	for (int i = 0; i < A.size(); i++)
		os << A[i] << " ";
	os << endl;
	return os;
}
template <>
ostream &operator<<(ostream &os, const vector< vector< int > > &A) {
	int N = A.size();
	int M;
	if (N > 0)
		M = A[0].size();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++)
			os << A[i][j] << " ";
		os << endl;
	}
	return os;
}

typedef pair< int, int > pii;
typedef long long ll;

struct edge {
	int from, to, d, c;
	edge(int _from = 0, int _to = 0, int _d = 0, int _c = 0) {
		from = _from;
		to = _to;
		d = _d;
		c = _c;
	}
	bool operator<(const edge &rhs) const {
		return (d == rhs.d) ? (c < rhs.c) : (d < rhs.d);
	}
};
struct aabb {
	int x1, y1, x2, y2;
	aabb(int x1, int y1, int x2, int y2) : x1(x1), y1(y1), x2(x2), y2(y2) {}
};

typedef vector< edge > edges;
typedef vector< edges > graph;
struct flow {
	int to, cap, rev, cost;
	flow(int to = 0, int cap = 0, int rev = 0, int cost = 0) : to(to), cap(cap), rev(rev), cost(cost) {}
};
typedef vector< vector< flow > > flows;

const int di[4] = {0, -1, 0, 1};
const int dj[4] = {-1, 0, 1, 0};
const int ci[5] = {0, 0, -1, 0, 1};
const int cj[5] = {0, -1, 0, 1, 0};
const ll LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const double PI = acos(-1);

int pow2(int n) { return 1LL << n; }
template < typename T, typename U >
bool chmin(T &x, const U &y) {
	if (x > y) {
		x = y;
		return true;
	}
	return false;
}
template < typename T, typename U >
bool chmax(T &x, const U &y) {
	if (x < y) {
		x = y;
		return true;
	}
	return false;
}

struct initializer {
	initializer() {
		cout << fixed << setprecision(20);
	}
};
initializer _____;

int N, M, K, T, Q, H, W;
signed main() {
	cin >> N;
	vector< bool > p(1e5 + 10, true);
	p[0] = false;
	p[1] = false;
	for (int i = 2; i < p.size(); i++)
		if (p[i])
			for (int j = i + i; j < p.size(); j += i)
				p[j] = false;
	vector< int > prime;
	rep(i, p.size()) if (p[i] == true) prime.push_back(i);
	int ans = 0;
	for (int i = N;; i++)
		if (p[i]) {
			ans = i;
			break;
		}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 512
import sys
from collections import defaultdict
def input(): return sys.stdin.readline().strip()
mod = 10**9+7

def main():
    N = int(input())
    A = list(map(int, input().split()))

    if N % 2 != 0:
        d = {2 * i: 0 for i in range(N // 2 + 1)}
        for a in A:
            try:
                d[a]  += 1
            except:
                print(0)
                return
        if d[0] != 1:
            print(0)
            return
        for key in d:
            if key == 0: continue
            if d[key] != 2:
                print(0)
                return
    else:
        d = {2 * i + 1: 0 for i in range(N // 2)}
        for a in A:
            try:
                d[a] += 1
            except:
                print(0)
                return
        for key in d:
            if d[key] != 2:
                print(0)
                return
    print(pow(2, N // 2, mod))

if __name__ == "__main__":
    main()


Measured memory_bytes: 91396
#include <iostream>
#include<vector>
#include <cmath>
#include <algorithm>
using namespace std;

int main() {
	char b;
	cin >> b;
	
	if (b == 'A') {
		cout << 'T' << endl;
	}
	else if (b == 'T') {
		cout << 'A' << endl;
	}
	else if (b == 'C') {
		cout << 'G' << endl;
	}
	else {
		cout << 'C' << endl;
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <functional>
#include <utility>
#include <cctype>
#include <fstream>

using namespace std;

#define ll long long
#define MOD 1000000007
#define INF 2000000000
#define LINF 9000000000000000000
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define du(x) cout<<#x<<'='<<x<<endl
#define du2(x,y) cout<<#x<<'='<<x<<' '<<#y<<'='<<y<<'\n'<<endl
#define du3(x,y,z) cout<<#x<<'='<<x<<' '<<#y<<'='<<y<<' '<<#z<<'='<<z<<'\n'<<endl
#define darr(arr,n) rep(i,(n-arr)){cout<<*(arr+i)<<' ';}cout<<endl
#define ddarr(arr,a,b) rep(i,a){rep(j,b){cout<<*(arr+i*b+j)<<' ';}cout<<endl;}
#define ddd ifstream in("Text.txt");cin.rdbuf(in.rdbuf());

vector<pair<int, int>>A;//文字、個数

int main() {
    int N, K;
    string S;
    cin >> N >> K >> S;
    //個数を入れる
    int cnt = 0;
    rep(i, N) {
        if (A.empty() || A.back().first != S[i]) {
            A.emplace_back(S[i], 1);
        }
        else {
            A.back().second++;
        }
    }


    int ret = 0, ptr = 0, sum = 0, all = 0;
    for (auto p : A) {
        while (ptr < A.size() && sum + (A[ptr].first == '0') <= K) {
            if (A[ptr].first == '0')sum++;//0であれば+1
            all += A[ptr].second;//個数を足す
            ptr++;//サイズの管理
        }
        ret = max(ret, all);
        if (p.first == '0')sum--;
        all -= p.second;
    }


    cout << ret << endl;
}


Measured memory_bytes: 1528
#include <iostream>
#include <cstdio>

#define R register

using namespace std;

int main() {
	
	int n;
	
	cin >> n;
	
	if(n < 1200)	cout << "ABC" << endl;
	else	if(n < 2800)	cout << "ARC" << endl;
	else	cout << "AGC" << endl;
	
	return 0;
	
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int N,M,K;
vector<int> G[3001];

int solve( vector<int>  used );

int getsize(const vector<int>& mt,const vector<int>& nt){
  int ret = 0;
  for(int i=0;i<N;i++) ret += mt[i];
  bool ok = true;
  for(int i=0;i<N;i++)
    if( nt[i] )
      for(int j=0;j<(int)G[i].size();j++)
        if( nt[G[i][j]] ) ok = false;
  if( ok ) return ret;
  return ret + solve(nt);
}

void dfs(int v,int t,vector<int>& g,vector<int>& k,const vector<int>& used){
  if( t ) g[v] = 1;
  else k[v] = 1;
  for(int i=0;i<(int)G[v].size();i++){
    int to = G[v][i];
    if( !used[to] || g[to] || k[to] ) continue;
    dfs( to, 1-t, g, k,used );
  }
}

int solve(vector<int> used){
  vector<int> g(N,0);
  vector<int> k(N,0);
  int res = 0;
  for(int i=0;i<N;i++){
    if( !used[i] || g[i] || k[i] ) continue;
    dfs(i,0,g,k,used);
    for(int i=0;i<N;i++)
      if( g[i] | k[i] ) used[i] = 0;
    res += min( getsize(g,k), getsize(k,g) );
    g=vector<int>(N,0);
    k=vector<int>(N,0);
  }
  return res;
}

int main(){
  cin >> N >> M >> K;
  for(int i=0;i<M;i++){
    int a,b; cin >> a >> b; --a; --b;
    G[a].push_back( b );
    G[b].push_back( a );
  }
  vector<int> used(N,1);
  for(int i=0;i<N;i++)
    if( G[i].empty() ) used[i] = 0;
  int res = solve(used);  
  // cout << res << endl;
  if( res > K ) cout << "Impossible" << endl;
  else cout << res << endl;
}

Measured memory_bytes: 1724
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main(){
  int n,m;
  cin>>n>>m;
  cout << n*(n-1)/2+m*(m-1)/2 << endl;
}

Measured memory_bytes: 3600
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL_DEBUG
  #include "LOCAL_DEBUG.hpp"
#endif
#define int long long

signed main(){

  string s; cin >> s;
  int k; cin >> k;

  vector<string> cand;
  int n = s.size();
  for(int i = 0; i < n; i++){
    for(int j = 1; j <= 5; j++){
      string t = s.substr(i, j);
      cand.push_back(t);
    }
  }
  sort(cand.begin(),cand.end());
  cand.erase(unique(cand.begin(),cand.end()),cand.end());
  cout << cand[k-1] << endl;

  return 0;
}


Measured memory_bytes: 1660
#include <bits/stdc++.h>
#define readvec(n,X,SX) \
    for(int i=1;i<=n;i++) { \
        cin >> X[i]; \
        SX[i] = SX[i - 1] + X[i];\
    }
using namespace std;
long long int N, M, A[200005], B[200005], result, SA[200005], SB[200005], K;
int main() {
    cin >> N >> M >> K;
    readvec(N, A, SA);
    readvec(M, B, SB);
    long long int MN = max(M, N);
    for(long long int i = N + 1; i <= MN + 1; i++)
        SA[i] = 1e16 + 1;
    for(long long int i = M + 1;i <= MN + 1; i++)
        SB[i] = 1e16 + 1;
    for(long long int i = 0; i <= N; i++)
        if(K >= SA[i])
            result = max(result,((upper_bound(SB, SB + MN + 1, K - SA[i])) - SB + i - 1));
    cout << result;
}


Measured memory_bytes: 9868
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n,m = list(map(int, input().split()))
uf = UnionFind(n)

for i in range(m):
    a,b = list(map(int, input().split()))
    uf.union(a-1,b-1)

ans = 0
for i in range(n):
    ans = max(ans, uf.size(i))

print(ans)


Measured memory_bytes: 14408
#include<stdio.h>

int main()
{
	char c;

	c = getchar();
	if (c == 'A')
		printf("T");

	if (c == 'G')
		printf("C");
	if (c == 'T')
		printf("A");

	if (c == 'C')
		printf("G");

	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <stdio.h>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <limits.h>
#include <math.h>
#include <functional>
#include <bitset>

#define repeat(i,n) for (long long i = 0; (i) < (n); ++ (i))
#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i] << '\n'
#define debugArrayP(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i].first<< " " << x[i].second << '\n'

using namespace std;

typedef long long ll;
typedef pair<int,int> Pii;
typedef vector<int> vint;
typedef vector<ll> vll;
const ll INF = LLONG_MAX/10;
const ll MOD = 1e9+7;

int main(){
  int N;cin >> N;
  vll h(N,0);
  vll c(N,1);
  vll T(N),A(N);
  repeat(i,N){
    cin >> T[i];
  }
  repeat(i,N){
    cin >> A[i];
  }
  repeat(i,N){
    if(i==0||T[i]>T[i-1]){
      c[i] = 1;
    }else{
      c[i] = T[i];
    }
    h[i] = T[i];
  }
  ll ans = 1;
  for(int i=N-1;i>=0;i--){
    if(c[i]==1){
      c[i]=h[i]<=A[i];
    }else if(i==N-1||A[i]>A[i+1]){
      c[i]=h[i]>=A[i];
    }else{
      c[i]=min(c[i],A[i]);
    }
    ans=ans*c[i]%MOD;
  }
  //debugArray(c,N);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
#include <atcoder/all>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,n) for (int64_t i=0; i<(n); ++i)
#define P pair<int,int>
using ll=int64_t;
using namespace std;
#define ketasuu(n) fixed<<setprecision(n)
#define btoe(p) p.begin(),p.end()
#define etob(p) p.rbegin(),p.rend()
#define chmax(x,y) x=max(x,y)




int main(){
    int n,q; cin>>n>>q;
    atcoder::dsu uf(n);
    rep(i,q){
        int a,b,c; cin>>a>>b>>c;
        if(a==0){
            uf.merge(b,c);
        }else{
            if(uf.same(b,c)){
                cout<<1<<endl;
            }else{
                cout<<0<<endl;
            }
        }
    }
}

Measured memory_bytes: 4008
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define erep(i,a,b) for(int i=a;i<=(int)(b);++i)
#define per(i,a,b) for(int i=(a);i>(b);--i)
#define eper(i,a,b) for(int i=(a);i>=b;--i)
#define pb push_back
#define mp make_pair
#define INF (1<<30)-1
#define MOD 1000000007
#define all(x) (x).begin(),(x).end()
#define vii vector<int>
#define vll vector<long long>
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a, b)*b;}

int N, A, B;
string s;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
    cin >> N >> A >> B;
    cin >> s;
    int ac = 0, foreign = 0;
    vector<string> ans(N, "No");
    rep(i, 0, N) {
        if (ac == A + B) break;
        if (s[i] == 'a') {
            ans[i] = "Yes";
            ac++;
        }
        else if (s[i] == 'b') {
            foreign++;
            if (foreign <= B) {
                ans[i] = "Yes";
                ac++;
            }
        }
    }
    rep(i, 0, N) 
        cout << ans[i] << endl;
    return 0;
}


Measured memory_bytes: 6224
from collections import deque

n = int(input())
music = deque([input().split() for _ in range(n)]) 
name = input()
for i in range(n):
  hoge = music.popleft()
  if(hoge[0] == name):
    print(sum([int(m[1]) for m in music]))
    exit()
print(0)

Measured memory_bytes: 3316
#include<iostream>
    #include<algorithm>
     
    using namespace std;
     
    long long int x1[100], y1[100], x2[100], y2[100];
     
    int main(){
     int N, M;
     cin >> N >> M;
     for(int i = 0; i < N; i++){
      cin >> x2[i] >> y2[i];
     }
     for(int i = 1; i <= M; i++){
      cin >> x1[i] >> y1[i];
     }
     for(int i = 0; i < N; i++){
      long long int ans, mini;
      mini = 1000000000LL;
      for(int j = 1; j <= M; j++){
       long long int hoge = abs(x1[j] - x2[i]) + abs(y1[j] - y2[i]);
       if(hoge < mini){
        mini = hoge;
        ans = j;
       }
      }
      cout << ans << endl;
     }
     return 0;
    }

Measured memory_bytes: 256
//In the Name of God
//Ya Ali

#include <bits/stdc++.h>

#define err(A) cout << #A << " = " << (A) << endl

using namespace std;

const int mod = 1e9 + 7;
const int maxn = (1 << 21) + 10;

int n;
int M;

int a[30][30];

int dp[maxn];
int len[maxn];

int32_t main()
{
  ios::sync_with_stdio(0); cin.tie(0);
  
  cin >> n;
  M = 1 << n;

  for (int i = 0; i < n; i ++)
    for (int j = 0; j < n; j ++)
      cin >> a[i][j];
  
  dp[0] = 1;
  for (int msk = 1; msk < M; msk ++)
    {
      len[msk] = len[msk / 2] + msk % 2; 
      for (int i = 0; i < n; i ++)
	if ((msk & (1 << i)) and a[i][len[msk] - 1])
	  dp[msk] = (dp[msk] + dp[msk ^ (1 << i)]) % mod;
    }

  cout << dp[M - 1] << endl;
    
  return 0;
}


Measured memory_bytes: 16640
#include <bits/stdc++.h>

int main() {
    int N;
    std::cin >> N;

    std::unordered_map<uint64_t, uint64_t> m;
    int a;
    for (int i = 0; i < N; ++i) {
        std::cin >> a;
        if (m.count(a) == 0) {
            m[a] = 1;
        } else {
            m[a] += 1;
        }
    }

    uint64_t cnt = 0; 
    for (const std::pair<uint64_t, uint64_t>& p : m) {
        if (p.first < p.second) {
            cnt += (p.second - p.first);
        } else if (p.first > p.second) {
            cnt += (p.second);
        }
    }

    std::cout << cnt << std::endl;


    return 0;
}


Measured memory_bytes: 4260
#include <fstream>
#include <iostream>

#include <cassert>
#include <climits>

#include <string>

#include <vector>
#include <map>
#include <deque>
#include <stack>

#include <algorithm>

#include <utility>

int main()
{
    int n, w;
    std::cin >> n >> w;
    assert(n >= 1 && n <= 100);
    assert(w >= 1 && w <= 10000);

    std::vector< std::pair<int, int> > items;
    items.push_back(std::make_pair(0, 0));
    for (int i = 1; i <= n; ++i)
    {
        int vi, wi;
        std::cin >> vi >> wi;
        assert(vi >= 1 && vi <= 1000);
        assert(wi >= 1 && wi <= 1000);

        items.push_back(std::make_pair(vi, wi));
    }

    std::vector< std::vector<int> > dp = std::vector< std::vector<int> >(n + 1, std::vector<int>(w + 1, 0));
    for (int i = 1; i < items.size(); ++i)
    {
        int value  = items[i].first;
        int weight = items[i].second;
        for (int j = 1; j <= w; ++j)
        {
            if ((j - weight) >= 0)
            {
                dp[i][j] = std::max(dp[i - 1][j], dp[i][j - weight] + value);
            }
            else
            {
                dp[i][j] = dp[i - 1][j];
            }
            
        }
    }

    std::cout << dp[n][w] << std::endl;
}



Measured memory_bytes: 6772
#include<bits/stdc++.h>

using namespace std;

int  N;

void input(){
  cin >> N; 
}

int main(){
  input();
  int ans;
  if(N%1000==0){
    ans = 0;
  }
  else{
    ans = 1000-N%1000;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3628
#include <iostream>
#include <string>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int x = 0;
    int m = 0;
    for (int i = 0; i < n; ++i) {
        char c;
        cin >> c;
        if (c == 'I') {
            ++x;
        } else {
            --x;
        }
        m = (x > m) ? x : m;
    }
    cout << m << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define INF 1000000009
//#define INF 9223372036854775807
typedef long long ll;
#define REP(i,n) for(int i=0;i<(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define rollcall cout<<"I'm Sucu."<<endl;
#define YES(s) s?cout << "YES" << endl:cout << "NO" << endl
#define Yes(s) s?cout << "Yes" << endl:cout << "No" << endl
#define Taka(s) s?cout << "Takahashi" << endl:cout << "Aoki" << endl
#define out(s,t,u) s?cout << t << endl:cout << u << endl
#define int ll
#define Endl endl

int N;
int A[214514];

int solve(int f){
    int sum=0;
   REP(i,N){
       sum+=abs(A[i]-f);
   }
   return sum;
}

signed main(void){
   cin >> N;
   REP(i,N){
       cin >> A[i];
       A[i]-=(i+1);
   }
   sort(A,A+N);
   
   
   //めぐる式(？)三分探索
   int ok=A[N-1],ng=A[0]-1,mid1,mid2;
    mid1=(ng+ng+ok)/3;
    mid2=(ng+ok+ok)/3;
   while(abs(ok-ng)>2){
       mid1=(ng+ng+ok)/3;
       mid2=(ng+ok+ok)/3;
       
       if(solve(mid1)<solve(mid2)){
           ok=mid2;
       }else{
           ng=mid1;
       } 
   }
   //おわり
   
   cout << min(min(solve(ok),solve(ng)),min(solve(mid1),solve(mid2))) << endl;
  return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>

using namespace std;

map<pair<int, int>, int> mp;

pair<int, int> StartAndEnd(int n){
    pair<int, int> p;
    p.first = p.second = n%10;
    while(n){
        p.first = n%10;
        n /= 10;
    }
    return p;
}

int main(){
    int n; cin >> n;
    
    for(int i = 1; i <= n; i++){
        pair<int, int> p = StartAndEnd(i);
        mp[p]++;
    }
    
    int sum = 0;
    for(auto it : mp){
        sum += it.second * mp[{it.first.second, it.first.first}];
    }
    
    cout << sum;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int P = sc.nextInt();

		double ans = 0;
		ans = Math.ceil((A*3 + P)/2);
		System.out.println((int)ans);
	}

}

Measured memory_bytes: 21844
n = int(input())
s = list(map(int, input().split()))

indexMin = 0
count = 0


for start in range(n):
    indexMin = s[start:].index(min(s[start:])) + start
    s[start], s[indexMin] = s[indexMin], s[start]
    if start != indexMin:
        count+=1

print(*s)
print(count)


Measured memory_bytes: 5608
#include <bits/stdc++.h>
using namespace std;

long long n, a, b, ans;

int main() {
 //   freopen("input.in", "r", stdin);
//    freopen("output.out", "w", stdout);

    scanf("%lld%lld%lld", &n, &a, &b);

    if (n == 1) ans = a == b;
    else {
        ans = (a <= b) * ((b - a) * (n - 2) + 1);
    }

    printf("%lld\n", ans);

    return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
//#define int ll
//#define endl '\n'

// use unique(x) - removec consecutive items, returns vec.begin() + number of items
// for vector: sort(all(vec)); vec.erase(unique(all(vec)), vec.end());
// use iota(all(vec), 0) for filling a vector with 0,1,2...
// use fill(all(vec), 1) for filling a vector with 1,1,1...
// use rotate(vec.begin(), vec.begin() + 1, vec.end()) to rotate a vector | middle arg becomes first
// print number in binary -> cout << bitset<20>(n);

const int N=101,W=100010;
const ll inf=1e18;
int n,m;
ll dp[N][W];
int w[N],v[N];

main(){
	cin.tie(0);cin.sync_with_stdio(0);
	cin>>n>>m;
	for(int i=0;i<n;++i)cin>>w[i]>>v[i];
	for(int i=0;i<=n;++i)
		for(int j=0;j<W;++j)
			dp[i][j]=inf;
	dp[0][0]=0;
	for(int i=0;i<n;++i)
		for(int j=0;j<W;++j){
			dp[i+1][j]=min(dp[i+1][j],dp[i][j]);
			if(j+v[i]<W)dp[i+1][j+v[i]]=min(dp[i+1][j+v[i]],dp[i][j]+w[i]);
		}
	ll res=0;
	for(int i=0;i<W;++i)if(dp[n][i]<=m)res=i;
	cout<<res<<endl;
}


Measured memory_bytes: 82532
#include<stdio.h>
int main(){
  
  int k=1,a,b,A=0,B=0,i;
  
  while(1){
    
    scanf("%d",&k);
    if(k==0){
      break;
    }
    
    for(i=0;i<k;i++){
      scanf("%d %d",&a,&b);
      if(a>b){
	A+=a+b;
      }
      else if(a<b){
	B+=a+b;
      }
      else{
	A+=a;
	B+=b;
      }
    }
    
    printf("%d %d\n",A,B);
    A=0;B=0; 
  }
  
  return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#ifdef ENABLE_DEBUG
#define dump(a) cerr<<#a<<"="<<a<<endl
#define dumparr(a,n) cerr<<#a<<"["<<n<<"]="<<a[n]<<endl
#else
#define dump(a) 
#define dumparr(a,n) 
#endif
#define FOR(i, a, b) for(ll i = a;i < b;i++)
#define For(i, a) FOR(i, 0, a)
#define REV(i, a, b) for(ll i = b-1;i >= a;i--)
#define Rev(i, a) REV(i, 0, a)
#define REP(a) For(i, a)
#define SIGN(a) (a==0?0:(a>0?1:-1))

typedef long long int ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<ll, ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;

const ll INF=(1LL<<50);
#if __cplusplus<201700L
ll gcd(ll a, ll b) {
  if(a < b) return gcd(b, a);
  ll r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}
#endif

template<class S,class T>
std::ostream& operator<<(std::ostream& os,pair<S,T> a){
  os << "(" << a.first << "," << a.second << ")";
  return os;
}
template<class T>
std::ostream& operator<<(std::ostream& os,vector<T> a){
  os << "[ ";
  REP(a.size()){
    os<< a[i] << " ";
  }
  os<< " ]";
  return os;
}

const long long MOD = 1000000007LL;

void solve(long long N, std::vector<long long> x){
  vector<ll> ans(N+1),sum(N+1),cache(N+1),cache2(N+1);
  ans[0]=sum[0]=0;
  cache[0]=cache[1]=1;
  cache2[N]=cache2[N-1]=1;
  REP(N){
    cache2[N-i-1]=cache2[N-i]*(N-i-1)%MOD;
  }
  REP(N){
    cache[i+1]=cache[i]*(i+1)%MOD;
    ans[i+1]=(sum[i]+cache[i+1])%MOD%MOD;
    sum[i+1]=(sum[i]*(i+1)%MOD+ans[i+1])%MOD;
  }
  dump(ans);
  dump(sum);
  dump(cache);
  dump(cache2);
  ll aans=0;
  REP(N-1){
    aans=(aans+ans[i+1]*cache2[i+2]%MOD*(x[i+1]-x[i])%MOD)%MOD;
  }
  cout<<aans<<endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> x(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&x[i]);
    }
    solve(N, std::move(x));
    return 0;
}


Measured memory_bytes: 4224
#include <iostream>
#include <cstdio>
#include <vector>
#include <array>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <sstream>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <random>
#include <bitset>
#include <cassert>
#include <tuple>
#include <list>
#include <iterator>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <complex>

using namespace std;

typedef long long ll;
typedef long double ld;

template<class htpe, class cmp>
using heap = priority_queue<htpe, vector<htpe>, cmp>;

template<class htpe>
using min_heap = heap<htpe, greater<htpe> >;

template<class htpe>
using max_heap = heap<htpe, less<htpe> >;

#define mp make_pair
#define pb push_back
#define mt make_tuple
#define ff first
#define ss second

#define forn(i, n) for (int i = 0; i < ((int)(n)); ++i)
#define forrn(i, s, n) for (int i = (int)(s); i < ((int)(n)); ++i)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

#define PYMOD(a, m) ((((a) % (m)) + (m)) % (m))

const int INF = 1791791791;
const ll INFLL = 1791791791791791791ll;

const int maxn = 379;
int dp[maxn][maxn][maxn];

int main() {
    // Code here:

    string s;
    cin >> s;
    int n = s.size();
    int k;
    cin >> k;

    for (int i = 1; i <= n; i++) {
        for (int j = n; j > i; j--) {
            for (int t = 0; t <= k; t++) {
                dp[i + 1][j][t] = max(dp[i + 1][j][t], dp[i][j][t]);
                dp[i][j - 1][t] = max(dp[i][j - 1][t], dp[i][j][t]);
                if (s[i - 1] == s[j - 1]) {
                    dp[i + 1][j - 1][t] = max(dp[i + 1][j - 1][t], dp[i][j][t] + 1);
                } else if (t > 0) {
                    dp[i + 1][j - 1][t - 1] = max(dp[i + 1][j - 1][t - 1], dp[i][j][t] + 1);
                }
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            ans = max(ans, 2 * dp[i][i][j] + 1);
            ans = max(ans, 2 * dp[i][i - 1][j]);
        }
    }

    cout << ans;

    return 0;
}


Measured memory_bytes: 169472
def cmb(n,r,b):
  if (r<0) or (n<r):
    return 0
  r=min(r,n-r)
  return fact[n]*factinv[r]*factinv[n-r]%p

p=10**9+7
N=10**6
fact=[1,1]
factinv=[1,1]
inv=[0,1]

for i in range(2,N+1):
  fact.append((fact[-1]*i)%p)
  inv.append((-inv[p%i]*(p//i))%p)
  factinv.append((factinv[-1]*inv[-1])%p)

X,Y=map(int,input().split())
ans=0
n=min(X,Y//2)
for i in range(n+1):
  XY=[X-i,Y-2*i]
  if XY[0]==2*XY[1]:
    j=XY[0]//2
    ans+=cmb(i+j,i,p)

print(ans)

Measured memory_bytes: 123768
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <string>

#define rep(i, a, b) for ( int i = (a); i < (b); i++ )
#define per(i, a, b) for ( int i = (b)-1; i >= (a); i--)
#define pb push_back
#define mp make_pair
#define bg begin()
#define en end()
#define all(v) (v).begin(), (v).end()
#define sz(v) (int)(v).size()

using namespace std;

typedef long long ll;
typedef long double ld;

using P = pair<int, int>;

static const long long MOD = 1000000007;
static const long long LINF = (ll)(1e18+99);
static const int INF = 1e9+99;

ll ans;

int main(void) {
    int n;
    cin >> n;
    vector<ll> dp(n+5);
    for (int i=1; i<=n+5; i++) {
        for (int j=i; j<=n+5; j+=i) {
            dp[j]++;
        }
    }

    rep(i, 1, n+1) ans += i*dp[i];

    cout << ans << "\n";
    return 0;
}



Measured memory_bytes: 81396
/*
　　こんにちは。あたしはｶｳｶﾞｰﾙ。
　　RedcoderになるためAtCoderを巡る旅をしてます。

　　　 　＿_
　　　 ヽ|＿_|ノ　　　　ﾓｫ
　　　　||‘‐‘||ﾚ　　_)_, ―‐ 、
　　　　/(Ｙ (ヽ＿ /・ ヽ　　   ￣ヽ
　　　　∠ ＿ ゝ　 ｀^ヽ ﾉ.::::_(ノヽ
　　　　 _/ヽ　 　　  /ヽ￣￣￣/ヽ
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define dump(x) cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl

#define rep(i, n) REP(i, 0, n)                  // 0, 1, ..., n-1
#define REP(i, x, n) for(int i = x; i < n; i++) // x, x + 1, ..., n-1
#define FOREACH(x, a) for(auto &(x) : (a))

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()

#define COUT(x) cout << (x) << endl

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() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int a, b; cin >> a >> b;
    COUT(max({a + b, a - b, a * b}));
}


Measured memory_bytes: 3652
N, M, K = list(map(int, input().split()))
mod = 10**9 + 7

tn = 0
tm = 0

for n in range(N):
    tn = (tn + n*(n+1)//2) % mod
tn = tn*M*M % mod

for m in range(M):
    tm = (tm + m*(m+1)//2) % mod
tm = tm*N*N % mod

class combinationmod():
    def __init__(self, MAX, mod):
        self.mod = mod
        self.fac = [0]*(MAX+1)
        self.finv = [0]*(MAX+1)
        self.inv = [0]*(MAX+1)
        self.fac[0] = self.fac[1] = 1
        self.finv[0] = self.finv[1] = 1
        self.inv[1] = 1
        for i in range(2, MAX+1):
            self.fac[i] = self.fac[i-1]*i % mod
            self.inv[i] = (-self.inv[mod % i]*(mod//i)) % mod
            self.finv[i] = self.finv[i-1] * self.inv[i] % mod
    def nCk(self,n,k):
        if n<k or n<0 or k<0:
            return 0
        return self.fac[n]*(self.finv[k]*self.finv[n-k]%self.mod)%self.mod
 
c = combinationmod(200000,int(1e9+7))

ans = (tn + tm)*c.nCk(N*M-2, K-2) %mod
print(ans)

Measured memory_bytes: 26740
#include <bits/stdc++.h>
using namespace std;
int main() {
  string s;
  cin >> s;
  int n = s.size(), c = 0;
  for(int i = 0; i < n; i++)c += (i + s[i]) % 2;
  cout << min(c, n - c) << endl;
}

Measured memory_bytes: 3768
#include <bits/stdc++.h>

using namespace std;

int main()
{
string S;
int a=0;
 cin >> S;
 for (int i= 0 ; i <S.size(); i++)
  {

    if (S.at(i)=='o')
    a=a+100;
 }
cout << a+700;






    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;

int main(){

  int n,k;

  string s;

  cin >>n>>k>>s;

  if(s.at(k-1)=='A')
    s.at(k-1)='a';
  else if(s.at(k-1)=='B')
   s.at(k-1)='b';
  else
    s.at(k-1)='c';
  
    cout << s << endl;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
prev = -1
res = 0
for x in a:
  res += b[x-1]
  if x == prev + 1:
    res += c[prev-1]
  prev = x
print(res)

Measured memory_bytes: 3064
#include <iostream>
using namespace std;

int main(void){
  int n;
  string l;
  int retval;
  int r,d,ld,rd;
  while(1){
    cin>>n;
    if(n==0)break;
    int grid[n+2][n+2];
    for(int i=0;i<n+2;i++){
      grid[i][0]=0;
      grid[0][i]=0;
      grid[i][n+1]=0;
      grid[n+1][i]=0;
    }
    for(int i=1;i<n+1;i++){
      cin>>l;
      for(int j=1;j<n+1;j++){
        grid[i][j]=l[j-1];
      }
    }
    retval=0;
    for(int i=1;i<n+1;i++){
      for(int j=1;j<n+1;j++){
        if(grid[i][j]=='0')continue;

        d=0;
        while(1){
          if(grid[i+d][j]=='1'){
            d++;
          }
          else{
            break;
          }
        }
        retval=max(retval,d);
        r=0;
        while(1){
          if(grid[i][j+r]=='1'){
            r++;
          }
          else{
            break;
          }
        }
        retval=max(retval,r);

        ld=0;
        while(1){
          if(grid[i+ld][j-ld]=='1'){
            ld++;
          }
          else{
            break;
          }
        }
        retval=max(retval,ld);

        rd=0;
        while(1){
          if(grid[i+rd][j+rd]=='1'){
            rd++;
          }
          else{
            break;
          }
        }
        retval=max(retval,rd);
      }
    }
    cout<<retval<<endl;
  }
}



Measured memory_bytes: 3316
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
const int INF = 1e9;
#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define SORT(a) sort(a.begin(),a.end())
using namespace std;
int main(){
    //Seiranchan!
    long long  n,m,mini,m_i;
    cin >> n>>m;

    long long  a[n],b[n],c[m],d[m];

    REP(i,n){
        cin >> a[i] >> b[i];
    }
    REP(i,m){
        cin >> c[i]>>d[i];
    }
    mini = INF;
    REP(j,n){
    REP(i,m){
        long long s = abs(a[j]-c[i]);
        long long t = abs(b[j]-d[i]);

        long long  ans = s+t;
        if(ans < mini){
            mini = ans;
            m_i =i;
        }
        
    }
    cout << m_i+1 << endl;
    mini=INF;
}
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;

int a[1111], b[1111], c[1111], d[1111], p[333], x, y, z;

int main(){
  
  while(cin >> a[0] >> b[0] >> c[0], *a+=*b+*c){
    for(int i=332;i;) p[i--] = 2;
    
    cin >> p[0];
    for(int i=0;i++<*p;) cin >> a[i] >> b[i] >> c[i] >> d[i];
    
    for(int i=0;i++<*p;){
      for(int j=0;j++<*p;){
	if(d[j]) p[a[j]] = p[b[j]] = p[c[j]] = 1;
	else{
	  if((x=p[a[j]]&1)&(y=p[b[j]]&1)) p[c[j]] = 0;
	  else if(x&(z=p[c[j]]&1)) p[b[j]] = 0;
	  else if(y&z) p[a[j]] = 0;
	}
      }
    }
    for(int i=0;i<*a;) cout << p[++i] << endl;
  }
  
}

Measured memory_bytes: 1172
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <iomanip>
#include <map>
using namespace std;

unsigned long long int a, b, c, d;
unsigned long long int sa;

long long int func(unsigned long long int x){
  unsigned long long int xn;
  xn = b / x - (a - 1) / x;
  return xn;
}

void solve(){
  cin >> a >> b >> c >> d;
  sa = b - a + 1;
  unsigned long long int cn, dn, cdn, cd;

  unsigned long long int x, y, r;
  if(c > d){
    x = c;
    y = d;
  }
  else{
    x = d;
    y = c;
  }
  r = x % y;
  while(r != 0){
    x = y;
    y = r;
    r = x % y;
  }

  cd = c * d / y;
  cn = func(c);
  dn = func(d);
  cdn = func(cd);
  //cout << sa << " " << cd << endl;

  cout << sa - (cn + dn - cdn) << endl;
  return;
}

int main(){
  solve();
  return 0;
}


Measured memory_bytes: 256
using System;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        const long INF = 1L << 60;
        var h = new long[1000010];
        var dp = new long[1000010];

        var N = int.Parse(Console.ReadLine());
        var input = Console.ReadLine().Split(" ").Select(int.Parse).ToArray();
        for (var i = 0; i < input.Length; ++i) h[i] = input[i];
        for (var i = 0; i < 1000010; ++i) dp[i] = INF;

        dp[0] = 0;

        for (var i = 1; i < N; i++)
        {
            dp[i] = new[] {dp[i], dp[i - 1] + Math.Abs(h[i] - h[i - 1])}.Min();
            if (i > 1) dp[i] = new[] {dp[i], dp[i - 2] + Math.Abs(h[i - 2] - h[i])}.Min();
        }

        Console.WriteLine(dp[N - 1]);
    }
}


Measured memory_bytes: 59560
#include <bits/stdc++.h>
using namespace std;

#ifdef WIN32
    #define lld "%I64d"
#else
    #define lld "%lld"
#endif

#define mp make_pair
#define pb push_back
#define put(x) { cout << #x << " = "; cout << (x) << endl; }

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef double db;

const int M = 1e6 + 15;
const int Q = 1e9 + 7;

vector<int> g[M];
int used[M], color[M];

int FL;
void dfs(int v, int c) {
	used[v] = 1;
	color[v] = c;
	for (auto u : g[v]) {
		if (!used[u]) {
			dfs(u, 1 - c);
		} else if (color[u] == c) {
			FL = 0;
		}
	}
}


int main() {
    srand(time(NULL));
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	//int n = 10;
	//int m = 10;
	int n, m;
	cin >> n >> m;
	//cout << n << " " << m << endl;
	for (int i = 0; i < m; i++) {
		int u = 0, v = 0;
		cin >> u >> v;
		
/*		while (u == v) {
			u = rand() % n + 1;
			v = rand() % n + 1;
		}
		cout << u << " " << v << endl;   */
		g[u].pb(v);
		g[v].pb(u);
//		is[u][v] = is[v][u] = 1;
	}
/*	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= n; k++) {
				for (int l = 1; l <= n; l++) {
					if (is[i][k] && is[j][l])
						G[{i, j}].pb({k, l});
				}
			}	
		}
	}

	int rans = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (!used2[i][j]) {
				dfs2(i, j);
				rans++;
			}
		}
	}
	cout << rans << endl;*/




	ll A = 0, B = 0;
	ll tmpN = n;
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		if ((int)g[i].size() == 0) {
			ans += tmpN * 2 - 1;
			tmpN--;
		}
	}
	for (int i = 1; i <= n; i++) {
		if (!used[i] && (int)g[i].size()) {
			FL = 1;
			dfs(i, 0);
			if (FL)
				A++;
			else
				B++;
			
		}
	}
	ans += (A + B) * (A + B) + A * A;
	cout << ans << endl;


    return 0;
}   

Measured memory_bytes: 36864
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<stack>
#include<set>
#include<climits>
#include<cstdlib>
#include<cmath>
#include<string>

using namespace std;

#define INF 1 << 29
#define LL long long int

LL const MOD = 1000000007;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    string str;
    cin >> str;

    vector<vector<LL>> dp(str.size()+1,vector<LL>(4,0));

    dp[str.size()][3] = 1;
    string abc = "ABC";

    for(int i = str.size()-1; i >= 0; i--){
        for(int j = 3; j >= 0; j--){
            if(j == 3){
                if(str[i] == '?'){
                    dp[i][j] = (dp[i+1][j]*3)%MOD;
                }else{
                    dp[i][j] = dp[i+1][j];
                }
            }else{
                dp[i][j] = (dp[i+1][j]*(str[i]=='?'?3:1)) + (dp[i+1][j+1]*((str[i]==abc[j]||str[i]=='?')?1:0));
                dp[i][j] %= MOD;
            }
        }
    }

    cout << dp[0][0] << endl;
    
    return 0;
}

Measured memory_bytes: 7376
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	
    public static void main(String[] args) throws IOException {
    	Scanner s = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		String[] input;
		int n = s.nextInt();
		List<Integer> list = new ArrayList<Integer>();
		int prev = 0;
		for (int i = 0; i < n; i++) {
			int x = s.nextInt();
			if (prev == x) {
				continue;
			}
			list.add(x);
			prev = x;
		}
		long ans = 0;
		long money = 1000;
		n = list.size();
		int start = 0;
		for (int i = 1; i < n; i++) {
			if (list.get(i) < list.get(i - 1)) {
				money = find(list, start, i - 1, money);
				start = i;
			}
		}
		money = find(list, start, n - 1, money);
		out.print(money);
		out.flush();
		out.close();
    }

	private static long find(List<Integer> list, int start, int end, long money) {
		long no = money / list.get(start);
		money -= no * list.get(start);
//		System.out.println(no + " " + (list.get(end) * no));
		return no * (long)(list.get(end)) + money;
	}
}


Measured memory_bytes: 36040
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <math.h>
#include <cmath>
#include <ctime>
#include <stdlib.h>

using namespace std;

#define int long long
#define endl "\n"
#define all(v)  v.begin(),v.end()
#define fir first
#define sec second
#define m_p make_pair
#define m_t make_tuple
#define rep(i,n)  for(int i=0; i<(int) (n); i++)


const double pai = 3.1415926535897;
const int mod = 1000000007;
const int INF = 1000000021;
const int MAX = 510000;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];


//x未満の要素数を返す二分探索関数
int b_s(vector<int>& vec, int xx) {
	return lower_bound(all(vec), xx) - vec.begin();
}
template<typename T>void vecout(vector<T>& vec) { for (T t : vec) cout << t << " "; cout << endl; }
template<typename TT>void vecin(vector<TT>& vec) {
	for (int i = 0; i < vec.size(); i++) {
		cin >> vec[i];
	}
}
template<class tt> struct counter {
	map<tt, int>mp;
	bool add(tt t, int xx) {
		if (!mp.count(t)) {
			mp[t] = xx;
			return true;
		}
		mp[t] += xx;
		if (!mp[t]) {
			mp.erase(t);
		}
		return false;
	}
};

// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

//n個を1個以上のx組のグループに分ける重複組み合わせはcom(n-1,x-1)
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
long long modpow(int a, int n) {
	int res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

bool chmax(int& xx, int yy) {
	if (xx < yy) {
		xx = yy;
		return true;
	}
	return false;
}
bool chmin(int& xx, int yy) {
	if (xx > yy) {
		xx = yy;
		return true;
	}
	return false;
}
int gcd(int xx, int yy) {
	int p = xx;
	int q = yy;
	if (q > p)swap(p, q);
	while (p % q != 0) {
		p %= q;
		swap(p, q);
	}
	return q;
}
int lcm(int xx, int yy) {
	return xx * yy / gcd(xx, yy);
}
bool prime(int xx) {
	if (xx <= 1) {
		return 0;
	}
	for (int i = 2; i * i <= xx; i++) {
		if (xx % i == 0) {
			return 0;
		}
	}
	return 1;
}



signed main() {
	int n, k,m=0;
	cin >> n >> k;
	vector<int>vec(n);
	rep(i, n) {
		cin >> vec[i];
		chmax(m, vec[i]);
	}
	int a1 = 0, a2 = m + 1,a3=1;//長さ
	while (a1 + 1 < a2) {
		a3 = (a1 + a2) / 2;
		int t = 0;//切る回数の和
		rep(j, n) {
			t += ceil(vec[j] / (long double)(a3 + 0.0))-1;
		}
		if (t > k) {
			a1 = a3;
		}
		else {
			a2 = a3;
		}
	}
	cout << a2 << endl;
}

Measured memory_bytes: 4832
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < (int)(n); i++)
#define repR(i, n) for(ll i = n; i >= 0; i--)
#define For(i, m, n) for(ll i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()

using namespace std;

ll gcd(ll a, ll b){
    ll r = a % b;
    while(r!=0){
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

ll lcm(ll x, ll y)
{
    if(x == 0 || y == 0) {
        return -1;
    }
    
    return (x * y / gcd(x, y));
}

ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

ll nCr(ll n, ll r) {
    if ( r * 2 > n ) r = n - r;
    ll dividend = 1;
    ll divisor  = 1;
    for ( ll i = 1; i <= r; ++i ) {
        dividend *= (n-i+1);
        divisor  *= i;
    }
    return dividend / divisor;
}

bool compare_by_b(pair<int, int> a, pair<int, int> b) {
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
}

ll mod = 1e9+7;

int main(){
    ll n;
    cin >> n;
    
    ll result = 0;
    For(i, 1, n){
        result += i;
    }
    
    cout << result << endl;
    
    return 0;
}






Measured memory_bytes: 256
a = int(input())
b,c = (int(x) for x in input().split())
lis =[]
lis = input().split()
lis = [int(s) for s in lis]

d = int(0)
e = int(0)
f = int(0)

for i in range(a):
  if lis[i] <= b:
    d += 1 
  elif b+1 <= lis[i] <= c:
    e += 1
  else:
    f += 1

if min(d,e,f,) > 0:
  print(min(d,e,f,))
else:
  print(0)

Measured memory_bytes: 3064
#include<iostream>
using namespace std;
int A[301][301];
int main()
{
    int N;
    cin>>N;
    for(int i=0;i<N;++i)
        for(int j=0;j<N;++j) cin>>A[i][j];
    long long x=0;
    for(int i=0;i<N;++i)
        for(int j=i;j<N;++j){
           int a=2e9;
            for(int k=0;k<N;++k)
                if(k!=i && k!=j) a=min(a,A[i][k]+A[k][j]);
            if(a>A[i][j]) x+=A[i][j];
            if(a<A[i][j]){
                cout<<-1<<endl;
                return 0;
            }
        }
    cout<<x<<endl;
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <cstdlib>
#include <queue>
#include <map>
#include <stack>
#include <set>
#define ll long long
using namespace std;

int main(){
  //cout<<123<<endl;
  int N,Y;
  cin>>N>>Y;
 
  for(int a=0;a<=N;a++){
    
    for(int b=0;b<=N-a;b++){
      
      int c=N-a-b;
      int now = 10000*a+5000*b+1000*c;
      if(now==Y) {
        cout<<a<<" "<<b<<" "<<c<<endl;
        return 0;
      }
    }
  }
  
    cout<<-1<<" "<<-1<<" "<<-1<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int main() {
  int a, b;
  //現在のレートa, 次回パフォーマンスb
  int G; //(a+b)/2;
  //次回レートG 出力がb
  cin >> a >> G ;
  b = G * 2 - a;
  
  cout << b << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(),x.end()
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define lop(i,s,t) for(int i=s;i<(t);++i)
#define rep(i,s,t) for(int i=s;i<=(t);++i)
#define dec(i,s,t) for(int i=s;i>=(t);--i)
using namespace std; 

/*
const int P=998244353; 
int sub(int a,int b){ a-=b; return a<0?a+P:a; }
int add(int a,int b){ a+=b; return a>=P?a-P:a; } 
int mul(int a,int b){ return 1ll*a*b%P; } 
int power(int a,int k){
	int res=1; 
	for(;k;k>>=1,a=mul(a,a))if(k&1)res=mul(res,a); 
	return res;
}
*/

const int N=1<<19; 

int n,a[N],m,b[N],c[N],d[N]; 

void upd(int &i,int p){
	if(a[p]>a[b[i]]){
		c[i]=b[i]; 
		b[i]=p;
	}else if(c[i]==-1||a[p]>a[c[i]]){
		c[i]=p;
	}
}

int main(int argc,char *argv[]){
#ifdef CURIOUSCAT
	//freopen("dat.in","r",stdin); 
#endif
	scanf("%d",&n); 
	m=1<<n;
	lop(i,0,m)scanf("%d",a+i),b[i]=i,c[i]=-1; 
	for(int s=1<<0;s<(1<<n);s<<=1){
		lop(i,0,m)if((i&s)==s){
			int p=i^s;
			upd(i,b[p]); 
			if(c[p]!=-1)upd(i,c[p]); 
		}
	}
	lop(i,1,m)d[i]=a[b[i]]+a[c[i]];
	lop(i,1,m)printf("%d\n",d[i]=max(d[i-1],d[i])); 
	return 0;
}


Measured memory_bytes: 10240
#include <bits/stdc++.h>
using namespace std;
long long mod = 1e9 + 7;
void add(long long &n , long long m){
    n += m;
    if(n >= mod){
        n -= mod;
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n , m ; cin>>n>>m;
    vector<long long>dp(n + 1);
    int br[100009] = {0};
    for(int i = 0 ; i < m; ++i){
        int x ; cin>>x;
        br[x] = 1;
    }
    dp[0] = 1;
    for(int i = 0 ; i <= n ; ++i){
        if(br[i] == 1)dp[i] = 0;
        for(int j : {1 , 2}){
            if(i + j <= n)add(dp[i + j] , dp[i]);
        }
    }
    cout<<dp[n]<<endl;
}


Measured memory_bytes: 1408
/**
 * Author RDP
 * 
**/
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
#include <bitset>
#define endl '\n'
#define bp(x) __builtin_popcount(x)
#define zf(x) __builtin_clz(x)
#define zl(x) __builtin_ctz(x)
#define par(x) __bultin_parity(x)
#define FAST_IO ios::sync_with_stdio(0); std::cin.tie(0);
typedef long long ll;
using namespace std;

void test_case()
{
    FAST_IO
    int n, m;
    cin >> n >> m;
    vector <int> num(n);
    ll votes = 0;
    for(int &x : num)
    {    cin >> x;
        votes += x;
    }
    int cnt = 0;
    float thres = 0.25 *  ( float(votes) / m );
    for(int x : num)
    {
        if( float(x) >=  thres)
            cnt ++;
    }
    if(cnt >= m)
        cout <<"Yes"<<endl;
    else 
        cout <<"No" <<endl;
    return ;
}
int main()
{
    FAST_IO
    test_case();
    return 0;
}

Measured memory_bytes: 256