akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  string S;
  cin >> N >> S;
  
  vector<char> list = {};
  
  for (int i=0; i<S.size(); i++) {
    list.push_back(S.at(i));
  }
  
  for (int i=0; i<S.size(); i++) {
    list[i] += N;
    if (list[i] >= 91) list[i] -= 26;
  }
  
  for (int i=0; i<S.size(); i++) {
    cout << char(list[i]);
  }
  
}


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

using namespace std;

typedef long long ll;
const ll INF = 1LL<<60;

ll gcd(ll a, ll b) {
  if(b == 0) return a;
  return gcd(b, a % b);
}

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

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

  int Q;
  cin >> Q;
  vector<vector<ll>> AB(Q);
  ll a, b;
  for(int i = 0; i < Q; i++){
    cin >> a >> b;
    AB[i].push_back(a);
    AB[i].push_back(b);
  }

  for(int i = 0; i < Q; i++){
    a = AB[i][0];
    b = AB[i][1];

    if(a > b){
      swap(a, b);
    }

    if(a == b){
      cout << (2 * a - 2) << endl;
    }else if(a+1==b){
      cout << (2 * a - 2) << endl;
    }else{
      ll c = floor(sqrt(a*b));
      if(c*c == a*b){
        c -= 1;
      }
      if(c*(c+1) >= a*b){
        cout << (2*c - 2) << endl;
      }else{
        cout << (2*c - 1) << endl;
      }
    }
  }
  return 0;
}


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

using namespace std;
using ll = long long;
using P = pair<ll, ll>;

const ll INF64 = 1LL << 60;
const int INF32 = 1 << 29;
const int MOD = 1000000007;

// Library

//
int main() {
#ifdef MYLOCAL
    ifstream in("input.txt");
    cin.rdbuf(in.rdbuf());
#endif
    int N, L ,T;
    cin >> N >> L >> T;
    vector<int> X(N);
    vector<int> W(N);
    for (int i = 0; i < N; ++i){
        cin >> X[i] >> W[i];
    }

    // ありのT秒後の位置
    // 円周上なのでリングバッファのようにmod
    vector<int> tmp(N);
    for (int i = 0; i < N; ++i) {
        if (W[i] == 1) {
            tmp[i] = (X[i] + T) % L;
        }
        else{
            tmp[i] = ((X[i] - T) % L + L) % L;
        }
    }
    sort(tmp.begin(), tmp.end());

    // 各ありが原点を何周したか数える
    int count = 0;
    for (int i = 0; i < N; ++i) {
        if (W[i] == 1){
            count -= (X[i] + T) / L;
        }
        else{
            count -= (X[i] - T - L + 1) / L;
        }
    }
    count = (count % N + N) % N;

    vector<int> ans(N);
    for (int i = 0; i < N; ++i){
        ans[(i + count) % N] = tmp[i];
    }

    for (int i = 0; i < N; ++i){
        cout << ans[i] << endl;
    }
    return 0;
}



Measured memory_bytes: 2816
#include <stdio.h>

int main(void) {
  int flag=0;
  int a, b, k;
  scanf("%d\n",&k);
  scanf("%d %d",&a,&b);
  for(int i=a;i<=b;i++){
    if(i%k==0){
      flag=1;
      break;
    }
  }
  if(flag){
    printf("OK");
  }else{
    printf("NG");
  }
  return 0;
}

Measured memory_bytes: 2148
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include <cassert>
#include <cmath>
#include<cstdint>

#define INF 1e9
#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<int,int>;

vector<int>bitSearch(int bit,int n){
    vector<int>S;
    rep(i,n)if(bit&(1<<i))S.push_back(i);
    return S;
}

int GCD(int a,int b){
    if(b==0)return a;
    return GCD(b,a%b);
}

int main(){
    int h,w;cin>>h>>w;
    vector<string>s(h);
    bool f[h][w];
    rep(i,h)rep(j,w)f[i][j] = false;
    rep(i,h)cin>>s[i];
    int dx[2] = {0,1};
    int dy[2] = {1,0};
    queue<P>que;
    que.emplace(0,0);

    while(!que.empty()){
        int y = que.front().first,x = que.front().second;
        f[y][x] = true;
        if(x==w-1 && y==h-1)break;
        que.pop();
        int cnt = 0;
        int nx,ny;
        rep(i,2){
            int xx = x+dx[i],yy = y+dy[i];
            if(xx<0 || xx>=w || yy<0 || yy>=h)continue;
            if(s[yy][xx]!='#')continue;
            ny = yy,nx = xx;
            cnt++;
        }
        if(cnt!=1){
            cout<<"Impossible"<<endl;
            return 0;
        }
        else que.emplace(ny,nx);
    }
    rep(i,h){
        rep(j,w){
            if(s[i][j]=='#' && !f[i][j]){
                cout<<"Impossible"<<endl;
                return 0;
            }
        }
    }
    cout<<"Possible"<<endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int nax = 1e5+5; //this should be const for the below values to be initialised
vector < int > edges[nax];
int indegree[nax];
int dist[nax];
bool vis[nax];

void dfs(int i) {
	vis[i] = true;
	for(int j : edges[i]) {
		dist[j] = max(dist[j],dist[i]+1);
		indegree[j]--;
		if(indegree[j] == 0)
			dfs(j);
	}
}
int main() {
	
	int n,m,a,b;
	cin>>n>>m;
	for(int i = 0 ; i < m ; i++) {
		cin>>a>>b;
		edges[a].push_back(b);
		indegree[b]++;
	}
	for(int i = 1 ; i <= n ; i++) {
		if(!vis[i] and indegree[i]==0) {
			dfs(i);
		}
	}
	int ans = 0;
	for(int i = 1 ; i<=n ; i++) {
		ans = max(ans,dist[i]);
	}
	cout<<ans;
	return 0;
}
//Errichto's code


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

int main(){
    long a, b, c, d, e, n;
    cin >> n >> a >> b >> c >> d >> e;
    long isMin = min({a, b, c, d, e});
    long ans = 0;
    if(n <= isMin){
        cout << 5 << endl;
        return 0;
    }else{
        if(n % isMin == 0){
            ans = n / isMin + 4;
        }else{
            ans = n / isMin + 5;
        }
    }
    cout << ans  << endl;
    return 0;
}


Measured memory_bytes: 768
#include<iostream>
#include<vector>

using namespace std;

int main(){
  int N,D; cin >> N >> D;
  vector<vector<int>>A(N,vector<int>(D));
  for(int i=0;i<N;i++){
    for(int j=0;j<D;j++){
      cin >> A[i][j];
    }
  }
  int dif;
  int ans=0;
  for(int i=0;i<N;i++){
    for(int j=i+1;j<N;j++){
      int n=0;
      for(int k=0;k<D;k++){
        dif=abs(A[i][k]-A[j][k]);
        n+=dif*dif;
      }
      bool flag=false;
      for(int k=0;k<=n;k++){
        if(k*k==n){
          flag=true;
        }
      }
      if(flag)ans++;
    }
  }
  cout << ans << endl;
  return 0;
}


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

int main(){
    int a, b, x;
    cin >> a >> b >> x;
    cout << (x>=a&&a+b>=x?"YES":"NO") << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long int ll;
#define FOR(i, a, b) for (ll i = (signed)(a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define EREP(i, n) for (int i = (n)-1; i >= 0; --i)
#define MOD 1000000007
#define pb push_back
#define INF 93193111451418101
#define MIN -93193111451418101
#define EPS 1e-11
#define lb(a, b) lower_bound((a).begin(), (a).end(), (b))
#define ub(a, b) upper_bound((a).begin(), (a).end(), (b))
#define bitcnt(a) (ll) __builtin_popcount((a))
using namespace std;
typedef pair<ll, ll> P;
typedef pair<ll, P> TP;
template <typename T> void fill_all(T &arr, const T &v) { arr = v; }
template <typename T, typename ARR> void fill_all(ARR &arr, const T &v) {
  for (auto &i : arr) {
    fill_all(i, v);
  }
}
//------------------変数-----------------------//

//-------------------関数----------------------//
string s;
int main() {
  cin >> s;
  ll itr = 0, cnt = 0; // g
  for (auto &a : s) {
    ll f = (a == 'g') + itr;
    cnt += (f == 2);
    cnt -= (f == 0);
    itr = 1 - itr;
  }
  printf("%lld\n", cnt);
}


Measured memory_bytes: 512
#include <stdio.h>
#include <string.h>

void ChangeLetter(char *str);
  
int main(){
  char W[10];
  char T[1000];
  char eof[] = {"END_OF_TEXT"};
  int count = 0;
  
  scanf("%s", W);
  ChangeLetter(W);

  while(1){
    scanf("%s", T);
    if(strcmp(T,eof ) == 0) break;
    ChangeLetter(T);
    if(strcmp(T, W) == 0) count++;
  }

  printf("%d\n", count);

  return 0;
}

void ChangeLetter(char *str){
  int i;
  for(i = 0;i < strlen(str);i++){
    if('a' <= str[i] && str[i] <= 'z'){
      str[i] -= 32;//全て大文字に変換
    }
  }
}



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

int main(){
  int a,b,t;
  cin >> a >> b >> t;
  t=t+0.5;
  int i=a,k=0;
  while(i<=1.0*(t+0.5)){
    i+=a;
    k+=b;
  }
  cout << k << endl;
  return 0;
}


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

using namespace std;

int H, L;
int p[1 << 19];
const int MOD = 1e9 + 7;
typedef long long LL;
int val[1 << 19];

template<typename T>
void upd(T &x,T y) {
	x += y;
	if (x >= MOD) x -= MOD;
}

vector<int>fuck;

void clear() {
	for (auto t:fuck) {
		val[t] = 0;
	}
	fuck.clear();
}

LL ans;

void solve(int now, LL fap, int flag) {
	//printf("solve %d %lld %d\n",now,fap,flag);
	fap = fap * now % MOD;
	if (now >= L) {
		int idx = now - L + 1;
		int nxt = now + p[idx] - idx;
		//printf("nxt = %d\n",nxt);
		if (flag == 1) {
			for (int i=nxt;i>=1;i>>=1) {
				fap = fap * i % MOD;
				upd(val[i], int(fap));
				fuck.push_back(i);
			}
		} else {
			assert(val[nxt] == 0);
			for (int i=nxt;i>1;i>>=1) {
				fap = fap * i % MOD;
				//printf("%d %lld %lld\n", i, fap, val[i] * fap % MOD);
				upd(ans, 1LL * val[i ^ 1] * (i / 2) % MOD * fap % MOD);
			}
		}
	} else {
		solve(now * 2, fap, flag);
		solve(now * 2 + 1, fap, flag);
	}
}

int main() {
	scanf("%d",&H);
	L = 1 << (H - 1);
	for (int i=1;i<=L;i++) {
		scanf("%d",&p[i]);
	}
	ans = 0;
	for (int LCA=1;LCA<L;LCA++) {
	//for (int LCA=1;LCA<=1;LCA++) {
		solve(LCA * 2, LCA, 1);
		solve(LCA * 2 + 1, 1, 2);
		//printf("!!!! %d %lld\n",LCA,ans);
		clear();
	}
	printf("%lld\n",ans);
}

Measured memory_bytes: 13000
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n); for(int i = 0;i < (int)(n);i++)
#define all(x) (x).begin(),(x).end()
typedef long long ll;

int main(){
    int n;
    cin >> n;
    int num[100000];
    rep(i,100000)num[i]=0;
    rep(i,n){
        int a;
        cin >> a;
        num[a]++;
    }
    int ans = 0;
    for(int i = 0;i < 100000-2;i++){
        int sum = num[i]+num[i+1]+num[i+2];
        ans = max(sum,ans);
        sum = 0;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
// define
#define int long long
#define UNIQUE(v) v.erase(unique(all(v)), v.end());
#define ZIP(v) sort(all(v)),UNIQUE(v)
#define ADD(a, b) a = (a + b) % mod
#define SUB(a, b) a = (a+mod-b)%mod
#define MUL(a, b) a = (((a)%mod) * ((b)%mod)) % mod
#define rollcall cout << "I'm Sucu." << endl;
#define repi(i,m,n) for(int i = m;i < n;i++)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) repi(i,1,n+1)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define dmp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define fi first
#define se second
// typedef
typedef complex<double> Point;
typedef pair<int, int> P;
typedef pair<int, P> PP;
typedef pair<P, int> Pi;
typedef vector<int> vi;
typedef deque<int> dq;
const int inf = 1e9+7;
const int INF = 1e18+7;
const int mod = 1e9+7;
// int sum = accumulate(a, a+n, 0LL);
// int mx = max_element(a, a+n);
// int mn = min_element(a, a+n);
// int cnt = count(a, a+n, k);

int A,B,C;

signed main()
{
    cin >> A >> B >> C;

    if(A==B&&A!=C)cout << "Yes\n";
    else if(B==C&&B!=A)cout << "Yes\n";
    else if(A==C&&B!=A)cout << "Yes\n";
    else cout << "No\n";
    return 0;
}

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

int main()
{
    int N;
    cin >> N;
    vector<long long> X(N);
    vector<long long> Y(N);

    for(int i = 0; i < N; ++i)
    {
        cin >> X[i];
      	Y[i] = X[i];
    }

    stable_sort(Y.begin(),Y.end());

    vector<size_t> index(X.size());
    iota(index.begin(), index.end(), 0);

    stable_sort(index.begin(), index.end(), [&X](size_t i1, size_t i2) {
        return X[i1] < X[i2];
    });

    vector<size_t> index2(X.size());
    for(int i = 0; i < N; ++i)
    {
        index2[index[i]] = i;
    }


    for(int i = 0; i < N; ++i)
    {
        if (index2[i] < N / 2)
        {
            cout << Y[N / 2] << endl;
        }
        else
        {
            cout << Y[N / 2 - 1] << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 8432
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define endl "\n"
#define debug(x) cout << #x << " = " << (x) << endl;
const ll MOD = 1000000007;

template<class T>
ostream& operator<<(ostream& os, vector<T> v) {
    cout << "[";
    for(auto &i: v) cout << i << ", ";
    cout << "]" << endl;
    return os;
}
template <typename K, typename V>
ostream& operator<<(ostream& os, pair<K, V> p) {
    os << "{" << p.first << ", " << p.second << "} ";
    return os;
}

int main() {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0); 
    
    string s;
    cin >> s;
    string ans = "No";
    for(auto i: s) if (i == '7') ans = "Yes";
    cout << ans << endl;
}

Measured memory_bytes: 3656
n,w=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]#w重さ v価値
dp=[[10**11+100 for _ in range(10**5+15)] for _ in range(n+1)]#各iで価値vを達成する最小のw
dp[0][0]=0
for i in range(n):#番目
  for j in range(10**5+15):#価値
      dp[i+1][j]=min(dp[i][j],dp[i][max(j-a[i][1],0)]+a[i][0])
an=0


for j in range(10**5+15):
  if dp[n][j]<=w and j>an:
    an=j
print(an)

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

int b[200000];
int main() {
	int a;
	scanf("%d", &a);
	for (int d = 0; d < a; d++) {
		int e;
		scanf("%d", &e);
		b[d] = e;
	}
	int p = INT_MIN;
	int s = 0;
	for (int f = a - 2; f != -1; f--) {
		s = max(s, b[f + 1]);
		p = max(p, s- b[f]);
	}
	cout << p << endl;
}

Measured memory_bytes: 3904
import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
                
        //a1 - an の読み込み
        int a[] = new int[n];
        for (int i = 0; i < n; i++){
            a[i] = sc.nextInt();
        }

        // 探索
        int count = 0;
        for (int i = 0; i < a.length; i++){
            if(i % 2 == 0 && a[i] % 2 == 1){
                count++;
            }
        }

        System.out.println(count);
    }
}


Measured memory_bytes: 27056
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,ll> P;

class segtree{
public:
	static const int N=1<<17;
	ll dp[1<<18];
	segtree(){
		for(int i=0;i<N*2;i++){
			dp[i]=(1LL<<60);
		}
	}
	void update(int k,ll v){
		k+=N-1;
		dp[k]=min(v,dp[k]);
		while(k>0){
			k=(k-1)/2;
			dp[k]=min(dp[k*2+1],dp[k*2+2]);
		}
	}

	ll query(int a,int b,int k=0,int l=0,int r=N){
		if(b<=l || r<=a)return (1LL<<60);
		if(a<=l && r<=b)return dp[k];
		int mid=(l+r)/2;
		ll vl=query(a,b,k*2+1,l,mid);
		ll vr=query(a,b,k*2+2,mid,r);
		return min(vl,vr);
	}
};

int n,m;
vector<P> G[100005]; 
segtree seg;

int main(void){
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		a--;
		b--;
		G[a].push_back(P(b,c));
	}
	seg.update(0,0);
	for(int i=0;i<n-1;i++){
		ll ic=seg.query(i,n);
		for(int j=0;j<G[i].size();j++){
			P p=G[i][j];
			int to=p.first;
			ll c=p.second;
			seg.update(to,ic+c);
		}
	}
	ll ans=seg.query(n-1,n);
	printf("%lld\n",ans==(1LL<<60)?-1:ans);
	return 0;
}


Measured memory_bytes: 7680
#include<bits/stdc++.h>
#define PI 3.141592653589793238462
using namespace std;
typedef long long ll;
typedef long double db;
multiset<int> s;
vector<int> r[300005];
int a[300005],b[300006],h,w,m,c[300005];
int main(){
    cin>>h>>w>>m;int ans=0;
    for(int i=1;i<=m;i++){
        cin>>a[i]>>b[i];
        r[a[i]].push_back(b[i]);
        c[b[i]]++;
    }s.insert(0);
    for(int i=1;i<=w;i++){
        if(c[i]>0) s.insert(c[i]);
    }
    for(int i=1;i<=h;i++){
        vector<int> p;int v=1;
        for(auto j:r[i]){
            s.erase(s.lower_bound(c[j]));
            p.push_back(c[j]);v=max(v,c[j]);
        }
        int x=r[i].size()+*s.rbegin();
        int y=r[i].size()+v-1;
        ans=max(ans,max(y,x));
        for(auto j:p){
            s.insert(j);
        }
    }
    cout<<ans<<endl;
} 

Measured memory_bytes: 37580
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define F first
#define S second
#define forn(i, n) for (int i = 0; i < (int)n; i++)
#define pb push_back
#define fastIO ios::sync_with_stdio(0), cin.tie(0);
#define endl '\n'
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
int main() {
#ifdef LOCAL
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
#else
    fastIO;
#endif
    int n;
    cin >> n;
    string s;
    cin >> s;

    int dif[n];
    int mx = 0;
    for (int i = 1; i < n; i++) {
        set<char> st;
        int ch[26];
        memset(ch, 0, sizeof ch);
        for (int j = 0; j < i; j++) {
            ch[s[j] - 'a'] = 1;
        }
        int cnt = 0;
        for (int j = i; j < n; j++) {
            if (ch[s[j] - 'a']) {
                cnt++;
                ch[s[j] - 'a'] = 0;
            }
        }
        mx = max(cnt, mx);
    }
    cout << mx << endl;
    return 0;
}

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

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

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

#define MAX 100005
#define INF 1001001001

int main(int, char**)
{
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a[i];

  int q;
  cin >> q;
  int b, e, k;
  rep(i,q) {
    cin >> b >> e >> k;
    cout << count(a.begin()+b, a.begin()+e, k) << endl;
  }

  return 0;
}



Measured memory_bytes: 3092
import bisect
A, B, Q = map(int, input().split())
INF = 10 ** 18
s = [-INF] + [int(input()) for i in range(A)] + [INF]
t = [-INF] + [int(input()) for i in range(B)] + [INF]
for q in range(Q):
    x = int(input())
    b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
    res = INF
    for S in [s[b - 1], s[b]]:
        for T in [t[d - 1], t[d]]:
            d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
            res = min(res, d1, d2)
    print(res)


Measured memory_bytes: 12804
#include "bits/stdc++.h"
using namespace std;
#define mx  100001
#define ll long long
#define llu long long unsigned
#define pb push_back
#define s(v) sort(v.begin(),v.end())


int main(){
    int n,x,t,cnt=0;
    cin>>n>>x>>t;
    if(n%x==0)cout<<(n/x)*t<<endl;
    else if(n%x!=0)cout<<(n/x+1)*t<<endl;
}
//1794102596


Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <algorithm>

#define ll long long
using namespace std;

ll mod = 1000003;

ll calc_pow(ll x, ll pow) {
    if (pow == 0) return 1;
    ll a = calc_pow(x, pow / 2);
    a = a * a % mod;
    if (pow % 2 == 1) a *= x;
    return a % mod;
}

ll waru(ll a, ll b) {
    return a * calc_pow(b % mod, mod - 2) % mod;
}

int main() {
    vector<ll> fact(mod);
    fact[0] = 1;
    for (int i = 1; i < mod; i++) fact[i] = fact[i - 1] * i % mod;

    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        ll x, d, n;
        cin >> x >> d >> n;
        if (d == 0)cout << calc_pow(x, n) << endl;
        else {
            ll a = waru(x, d);
            if (a + n - 1 >= mod)cout << 0 << endl;
            else {
                cout << waru(fact[a + n - 1], fact[a - 1]) * calc_pow(d, n) % mod << endl;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 8704
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
from collections import Counter, deque
import itertools
#from scipy.misc import comb

N,x = map(int, input().split())
A = list(map(int, input().split()))

ans = 0
for i in range(N-1):
    sumc = A[i]+A[i+1]
    if sumc > x:
        ans += (sumc-x)
        A[i+1] = max(A[i+1]-(sumc-x), 0)

print(ans)

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

const int MAX_N = 5010;

int main() {
    ios::sync_with_stdio(false);
    set<string> strings;
    string s;
    cin>>s;
    int k;
    cin>>k;

    int n = s.size();

    for(int i = 0;i<n;++i) {
       for(int j = 1;j <= 5 && i+j <= n;++j) {
            strings.insert(s.substr(i, j));
       }
    }

    string res;

    for(string s: strings) {
        if(k == 1) {
            res = s;
            break;
        }
        k--;
    }

    cout<<res<<endl;
    return 0;
}


Measured memory_bytes: 1664
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		if(a+b+c>=22)System.out.println("bust");
		else System.out.println("win");

	}

}


Measured memory_bytes: 21844
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

int readint() {
    return readln.chomp.to!int;
}

int[] readints() {
    return readln.split.map!(to!int).array;
}

void main() {
    auto nq = readints();
    int n = nq[0], q = nq[1];

    auto bit = new BinaryIndexTree(n);
    for (int i = 0; i < q; i++) {
        auto xs = readints();
        switch (xs[0]) {
        case 0: // add
            bit.add(xs[1], xs[2]);
            break;
        case 1: // sum
            int sum = bit.sum(xs[2]) - bit.sum(xs[1] - 1);
            writeln(sum);
            break;
        default:
            break;
        }
    }
}

class BinaryIndexTree {
    private int[] _bit;

    this(int n) {
        _bit = new int[n + 1];
    }

    int sum(int p) {
        int s = 0;
        while (p > 0) {
            s += _bit[p];
            p -= p & -p;
        }
        return s;
    }

    void add(int p, int x) {
        while (p < _bit.length) {
            _bit[p] += x;
            p += p & -p;
        }
    }
}

Measured memory_bytes: 3716
import java.io.*;
import java.util.*;


public class Main {

	private static Scanner sc;
	private static Printer pr;

	private static void solve() {
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		int d = sc.nextInt();

		if (a * b >= c * d) {
			pr.println(a * b);
		} else {
			pr.println(c * d);
		}
	}

	// ---------------------------------------------------
	public static void main(String[] args) {
		sc = new Scanner(System.in);
		pr = new Printer(System.out);

		solve();

		pr.close();
		sc.close();
	}

	private static class Printer extends PrintWriter {
		Printer(PrintStream out) {
			super(out);
		}
	}
}


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

using namespace std;

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

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

struct UnionFind {
    UnionFind(int n) {
        rank.assign(n, 0);
        parent.resize(n);
        num.assign(n, 1);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (x == parent[x])
            return x;
        return parent[x] = find(parent[x]);
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    void unit(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y)
            return;

        if (rank[x] < rank[y]) {
            parent[x] = y;
            num[y] += num[x];
        }
        else {
            parent[y] = x;
            num[x] += num[y];
            if (rank[x] == rank[y])
                rank[x]++;
        }
    }

    vector<int> rank;
    vector<int> parent;
    vector<int> num;
};

pll E[100005];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, M;
    cin >> N >> M;
    REP(i, M) {
        cin >> E[i].first >> E[i].second;
        E[i].first--;
        E[i].second--;
    }

    UnionFind uf(N);

    vector<ll> v;
    ll p = N * (N - 1) / 2;
    for (ll i = M - 1; i >= 0; --i) {
        v.push_back(p);
        if (uf.same(E[i].first, E[i].second))
            continue;

        ll x = uf.find(E[i].first);
        ll y = uf.find(E[i].second);
        p -= uf.num[x] * uf.num[y];
        uf.unit(x, y);
    }

    reverse(v.begin(), v.end());
    REP(i, v.size()) {
        cout << v[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 4980
/* ex4_1
  sachiyan */

#include <stdio.h>
int main(void){
    int number, watched; //NとDを定義する
    int answer; //answerを定義する
    scanf("%d %d", &number, &watched); //NとDの入力を読み取る
    if( number % (2*watched+1) != 0){ //2D+1は一人の監視員が見れる木の数
        answer = number / (2*watched+1) + 1; //一人当たりみれる木の数の倍数でなければ、もう一人必要
        printf("%d\n", answer); //answerを出力
    }
    else{
        answer = number / (2*watched+1); //そうでなければ、一人当たりみれる木の数の何倍かが答え
        printf("%d\n", answer); //answerを出力
    }


    return 0;
}


Measured memory_bytes: 128
import java.util.*;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String a = sc.next();
    String b = sc.next();
    String c = sc.next();
    String one = a.substring(a.length()-1);
    String two = b.substring(0,1);
    String three = b.substring(b.length()-1);
    String four = c.substring(0,1);

    if (one.equals(two) && three.equals(four)) {
      System.out.println("YES");
    } else {
      System.out.println("NO");
    }
  }

}


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

using namespace std;

long long int gcd(int a,long long int b)
{
	long long int ans,x;
	int tmp,r;
	x = a * b;
	if(a<b){
		tmp = a; a = b; b = tmp;
	}
	r = a%b;
	while(r != 0){
		a = b; b = r; r = a % b;
	}
	ans = x/b;
	return ans;
}
int main(void)
{
	int n,m;
	cin>>n>>m;
	int a[n],i;

	for(i=0;i<n;i++){
		cin>>a[i];
	}
	long long int ans = a[0]/2;
	for(i = 1; i < n; i++){
		ans = gcd(a[i]/2,ans);
	}
	int j = 1;
	int count = 0;
	int k;
	
	for(i = 0; i < n; i++){
		k = ans / (a[i]/2);
		if(k % 2 == 0){
			cout<<"0"<<endl;
			return 0;
		}
	}
	
	for(i = ans; i <= m; i = ans * j){
		j += 2;
		count++;
	}
	cout<<count<<endl;
	
	return 0;
}




Measured memory_bytes: 640
//int a = stoi(c); 文字列をintへ
//小文字から大文字
//transform(a.begin(), a.end(), a.begin(), ::toupper);
//途中の出力をそのまま残さない
//数値計算 個数以外はdouble
//map<キー,値> p は辞書。p[キー] = 値
//map 全探索
//auto begin = p.begin(), end = p.end();
//for (auto it = begin; it != end; it++) {}
//mapのキー：it->first mapのバリュー：it->second
//絶対値 abs()
//入力は空白で切れる
//大文字判定 isupper(文字) 小文字判定 islower(文字)
//do{}while(next_permutation(ALL(配列)))
//while(N)で回すとき、Nはコピーを作っておく
//小文字に対応する文字コード：S[i] - 'a'
//文字コード→小文字：(char)(数字+'a')
//グラフの距離:隣接行列で扱う
//等価なものに変換する思考
//bool型　初期値はTrue
//島渡りの問題：中間ノードに着目
//配列はvector<>を使う：意味わからないエラーがなくなる。
//背反な事象にちゃんとわける
//チェックリストはマップを使う
//数が大きい時の比較はstring型で行う
//全て0になったか調べたい->0になるたびにcntする
//またはかかつか
//例外処理は最初にする
#include <bits/stdc++.h>
#define rep(i,N) for(int i = 0; i < N;i++)
#define ALL(a) (a).begin(),(a).end()
#define ll long long int
using namespace std;

//円周率
const double PI = 3.14159265358979323846;
//割るやつ
const ll M = (pow(10, 9) + 7);

// K進数でのNの桁数
ll dig(ll N, ll K) {
	ll dig = 0;
	while (N) {
		dig++;
		N /= K;
	}
	return dig;
}
// a,bの最大公約数
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}

ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}

//nC2の計算
ll C(ll N) {
	return N * (N - 1) / 2;
}

//階乗計算
ll f(ll n) {
	if (n == 0 || n == 1) return 1;
	else return (n * f(n - 1)) % M;
}

int main() {
	ll a, b, c; cin >> a >> b >> c;
	ll  d = c - a - b;
	if (d > 0 && 4 * a * b <d*d )cout << "Yes" << endl;
	else cout << "No" << endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Numerics;

namespace Atcoder {
    class Program {
        static void Main(string[] args) {
            //var N = int.Parse(Console.ReadLine());
            //var inputList = new List<int>();
            //foreach (var i in Enumerable.Range(0, N))
            //    inputList.Add(int.Parse(Console.ReadLine()));


            var NM = Console.ReadLine().Split(' ');
            var N = long.Parse(NM.First());
            var M = long.Parse(NM.Last());

            long result = 0;
            if (N == 1 && M == 1)
                result = 1;
            else if ((N == 1 && M != 1))
                result = M - 2;
            else if (N != 1 && M == 1)
                result = N - 2;
            else if (N >= 2 && M >= 2)
                result = (N - 2) * (M - 2);

            Console.WriteLine(result);

            //var NK = Console.ReadLine().Split(' ');
            //var N = int.Parse(NK.First());
            //var K = int.Parse(NK.Last());

            //long count = 0;
            ////count += (N - K - 1) * (N - K);
            //count += Factorial(N - K);
            //if (K == 0)
            //    count += N;
            //else
            //    for (int a = K; a < N; a++) {
            //        for (int b = K; b < a; b++) {
            //            if (a % b == 0) {
            //                // Console.WriteLine("{0} {1}", a, b);
            //                count++;
            //            }
            //        }
            //    }
            //Console.WriteLine(count);
            return;
        }

        //public static BigInteger Factorial(int n) {
        //    if ((n & 1) == 0) return Factorial(n / 2).Square() * Combination(n, n / 2);
        //    else return Factorial(n / 2).Square() * Combination(n, n / 2) * (n - n / 2);
        //}
    }
}


Measured memory_bytes: 11220
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    string a;
    cin >> a;
    string ans;

    if(a == "Sunny"){
        ans = "Cloudy";
    }else if(a == "Cloudy"){
        ans = "Rainy";
    }else{
        ans = "Sunny";
    }
    cout << ans << endl;
}

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

using namespace std;

typedef long long ll;
typedef long double ld;

const int mod = 1e9 + 7;
int n, m;
char arr[1005][1005];
int dp[1005][1005];

int solve(int i, int j)
{
  if(i >= n || j >= m || arr[i][j] == '#')
    return 0;
  if(i == n - 1 && j == m - 1)
    return 1;
  int &ans = dp[i][j];
  if(ans != -1)
    return ans;
  return ans = (solve(i + 1, j) + solve(i, j + 1)) % mod;
}
int main()
{
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  for(int i = 0; i < n; i++)
    for(int j = 0; j < m; j++)
      cin >> arr[i][j];
  memset(dp, -1, sizeof(dp));
  cout << solve(0, 0);
  return 0;
}


Measured memory_bytes: 5248
k, a, b = [int(item) for item in input().split()]
num = 1
# Trade is worse
if b - a <= 2:
    print(k+1)
    exit()
if k < a - 1 + 2:
    print(k+1)
    exit()
k -= (a - 1)
print(a + k // 2 * (b-a) + k % 2)

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

#define FOR(i,a,b) for(int i=int(a);i<int(b);++i)
#define RFOR(i,a,b) for(int i=int(b)-1;i>=int(a);--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)

int q;

int main() {
    int a,b;
    string str,q_str,m_str;
    cin >> str;
    cin >> q;
    REP(i,q) {
        cin >> q_str;
        cin >> a >> b;
        if (q_str=="print") {
            cout << str.substr(a,b-a+1) << endl;
        } else if (q_str=="replace") {
            cin >> q_str;
            m_str = str.erase(a,b-a+1);
            str = m_str.insert(a,q_str);
        } else {
            reverse(str.begin()+a,str.begin()+b+1);
        }
        //cout << str << endl;
    }
    return 0;
}



Measured memory_bytes: 3224
#create date: 2020-08-22 21:00

import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n = ns()
    s = 0
    for i in n:
        s += int(i)
    print("Yes" if s % 9 == 0 else "No")

if __name__ == "__main__":
    main()

Measured memory_bytes: 68000
#include<bits/stdc++.h>
using namespace std;
#ifndef d
#define d(...)
#endif
#define st first
#define nd second
#define pb push_back
#define siz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
typedef long long LL;
typedef long double LD;
constexpr int INF=1e9+7;
constexpr LL INFL=1e18;
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.st << "," << P.nd << ")";
}
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag,
         tree_order_statistics_node_update>;
*/

constexpr int maxn = 100005;

int n, m, deg[maxn], par[maxn];
vector<int> G[maxn];


int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	for(int i=0; i<n+m-1; i++) {
		int a, b; cin >> a >> b;
		G[a].pb(b);
		deg[b]++;
	}
	queue<int> q;
	q.emplace(find(deg+1, deg+n+1, 0) - deg);
	while(not q.empty()) {
		auto w = q.front(); q.pop();
		for(auto v:G[w]) {
			if(--deg[v] == 0) {
				q.emplace(v);
				par[v] = w;
			}
		}
	}
	
	for(int i=1; i<=n; i++)
		cout << par[i] << "\n";

	return 0;
}


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

#define ll long long 
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
#define all(x) (x).begin (),(x).end()
#define f(i, a, b) for (int i=a; i<(signed)(b); ++i)
#define pc __builtin_popcount // counts number of 1's in bin(num)

const double pi = 2*acos(0.0);
//__gcd(n1, n2);
//cout << fixed;
//cout << setprecision(6); //fixes # of dp



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

    int n, k;
    cin >> n >> k;
    int ans = 0;
    while(n >= k){
        n = n/k;
        ans++;
    }
    if(n!=0){
        ans++;
    }
    cout << ans;
}








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

#define ll          long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<int,pii>    
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define hell        1000000007
#define endl        '\n'
#define rep(i,a,b)  for(int i=a;i<b;i++)
using namespace std;
int v[100005];
vi x(100001),y(100001);
vi X[1001],Y[1001];
char c[100001];
void solve()
{
    int n,k,ans=0,cnt=0;
    cin>>n>>k;
    rep(i,0,n){
        cin>>x[i]>>y[i]>>c[i];
        X[x[i]%k].pb(i);
        Y[y[i]%k].pb(i);
        if((x[i]/k+y[i]/k)%2==0) v[i]=1;
        if(v[i] && c[i]=='B') cnt++;
        if(v[i]==0 && c[i]=='W') cnt++;
    }
    ans=cnt;
    rep(a,0,k){
        int temp[n+1],tempcnt=cnt;
        rep(i,0,n){
            temp[i]=v[i];
        }
        rep(b,0,k){
            for(auto i:Y[b]){
                v[i]=!v[i];
                if(v[i] && c[i]=='B') cnt++;
                else if(v[i]==0 && c[i]=='W') cnt++;
                else cnt--;
            }
            ans=max(ans,cnt);
            ans=max(ans,n-cnt);
        }
        cnt=tempcnt;
        rep(i,0,n){
            v[i]=temp[i];
        }
        for(auto i:X[a]){
            v[i]=!v[i];
            if(v[i] && c[i]=='B') cnt++;
            else if(v[i]==0 && c[i]=='W') cnt++;
            else cnt--;
        }
        ans=max(ans,cnt);
        ans=max(ans,n-cnt);
    }
    cout<<ans;
} 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)
        solve();
    return 0;
}

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

int main(){
  int n;
  cin >> n;
  vector<vector<int> > abc(n, vector<int>(3, 0));
  for(int i = 0; i < n; i++)  for(int j = 0; j < 3; j++)  cin >> abc[i][j];

  vector<vector<int> > dp(n, vector<int>(3, 0));

  //dp[i][0] = max happiness if swim today.        dp[i][0] = max (dp[i - 1][1] + abc[i][0], dp[i - 1][2] + abc[i][0])
  //dp[i][1] = max happiness if catch bugs today.  dp[i][1] = max (dp[i - 1][0] + abc[i][1], dp[i - 1][2] + abc[i][1])
  //dp[i][2] = max happiness if do homework today. dp[i][2] = max (dp[i - 1][0] + abc[i][2], dp[i - 1][1] + abc[i][2])

  dp[0][0] = abc[0][0];
  dp[0][1] = abc[0][1];
  dp[0][2] = abc[0][2];


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

  cout << max ({dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]}) << endl;
  return 0;
}


Measured memory_bytes: 11136
#include<iostream>
using namespace std;
int main(){
	int n=0;
	cin>>n;
	int a,b,c;
	int x,y,z;
	for(int i=1;i<=n;i++){
		cin>>a>>b>>c;
		if(a*a==b*b+c*c||b*b==a*a+c*c||c*c==a*a+b*b)cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
}

Measured memory_bytes: 0
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_C main
#include "bits/stdc++.h"
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LLONG_MAX/2)
const int MGN = 8;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using psi = pair<string, int>;
// functions

#endif


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

    int N; cin >> N;
    vi S(N+MGN,0); FOR(i, 1, N+1) cin >> S[i];

    const int SMAX = 100;
    vvb dp(N + MGN, vb(SMAX*N + MGN, false));
    // dp[i][j] := can make sum j when taking items from {S[1],...S[i]}
    dp[0][0] = true;

    FOR(i,0,N+1) {
        for (int j = SMAX * i; j >= 0; j--) {
            if (dp[i][j]) {
                dp[i + 1][j] = dp[i][j]; // not take S[i+1]
                dp[i + 1][j + S[i+1]] = dp[i][j]; // take S[i+1]
            }
        }
    }

    int ans = 0;
    for (int j = SMAX * N; j >= 0; j--) {
        if (dp[N][j] && j%10!=0) {
            ans = j;
            break;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 384
using System;
using System.Collections.Generic;
class Program
{
	static long[,] dp;
	//static	List<List<long>> dp;
	static int[] weight, value;
	static long INF_LONG = long.MaxValue/2;
    //static List<string> str = new List<string>();
	static void Main(string[] args)
	{
		// 入力フェーズ
		//int N = Int32.Parse(Console.ReadLine());
		string[] input = Console.ReadLine().Split(' '); // N,W
		int N = Int32.Parse(input[0]);
		int W = Int32.Parse(input[1]);
		weight = new int[N];
		value = new int[N]; // 重さと価値の入力値
		for(int i=0; i<N; i++){
			string[] items = Console.ReadLine().Split(' ');
			weight[i] = Int32.Parse(items[0]);
			value[i] = Int32.Parse(items[1]);
		}
//Console.WriteLine(weight[0] + "");

//i番目までの品物のうち、価値の総和がj以上になるように選んだ時の重さの総和の最小値
		dp = new long[N+1,N*1000+1];
		for(int i=1; i<=N; i++)
		{
			for(int j=0; j<=N*1000; j++)
			{
				dp[i,j] = INF_LONG; //大きい数で初期化する
			}
		}
		HashSet<int> hs = new HashSet<int>();
		hs.Add(0);
		for(int i=1; i<=N; i++)
		{
			// i番目までの品物から選ぶ
			HashSet<int> loopHs = new HashSet<int>(hs);
			hs.Clear();
			foreach(int j in loopHs)
			{
				// i番目の品物を選ばない場合→価値の総和も重さの総和も変わらず(i-1と)
				dp[i,j] = Math.Min(dp[i-1, j], dp[i,j]); // 更新した方が小さくなるなら更新する

				hs.Add(j);

				// 選ぶ場合→価値も重さも増える
				// もし重さが制限を超えるようなら考慮する必要ないのでスルーする
				long ww = dp[i-1,j] + weight[i-1];

				if(ww > W)
				{
					continue;
				}
				else
				{
					dp[i, j+value[i-1]] = Math.Min(ww, dp[i,j+value[i-1]]);
					hs.Add(j+value[i-1]);
				}
			}

		}

		// N番目までの品物から選んで、価値の大きい順に見ていってW以下になったところの価値を表示する
		for(int j=N*1000; j>=0; j--)
		{
			if(dp[N, j] <= W)
				{
					Console.WriteLine(j + "");
					return;
				}
		}
  }
}


Measured memory_bytes: 118488
N, K = map(int, input().split())
x = list(map(int, input().split()))
left = []
right = []
cnt = 0
for i in range(N):
    if x[i] < 0:
        left += [-x[i]]
    elif x[i] > 0:
        right += [x[i]]
    else:
        cnt += 1
rest = K - cnt
left = left[::-1]
if rest != 0:
    ans = float('inf')
else:
    ans = 0
    print(ans)
    exit()

for i in range(rest+1):
    if i == 0 and len(right) >= rest:
        ans = min(ans, right[rest-1])
    elif rest-i == 0 and len(left) >= i:
        ans = min(ans, left[rest-1])
    elif len(left) >= i and len(right) >= rest-i:
        ans = min(ans, left[i-1]+right[rest-i-1]+min(left[i-1], right[rest-i-1]))

print(ans)

Measured memory_bytes: 14252
#pragma GCC optimize ("Ofast")
#include "bits/stdc++.h"
	
#define PI 3.141592653589793
#define FAST ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
// Use for file I/O;
#define FIN string _fname = "paintbarn"; \
			string _is = _fname + ".in", _os = _fname + ".out"; \
			freopen(_is.c_str(), "r", stdin); \
			freopen(_os.c_str(), "w", stdout);

typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;

using namespace std;

const ll INF = 1e9 + 10;
const ll INF2 = 3e18 + 10;
const int MOD = 1e9 + 7;
const ld EPS = 1e-4;

const int LOGN = 19;
const int MAXN = 305;


int cnt[4];
ld p[MAXN][MAXN][MAXN], ev[MAXN][MAXN][MAXN];


int main() {
	FAST;

	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		cnt[a]++;
	}

	p[cnt[1]][cnt[2]][cnt[3]] = 1;
	for (int c = n; c >= 0; c--) {
		for (int b = n; b >= 0; b--) {
			for (int a = n; a >= 0; a--) {
				if (a + b + c > n) continue;
				if (a + b + c == 0) continue;
					
				ld p_waste = (ld) (n - a - b - c) / n;
				ld ev_waste = p_waste / (1.0L - p_waste);
				ev[a][b][c] += ev_waste * p[a][b][c];

				if (a) {
					ld pp = (ld) a / (a + b + c);
					p[a - 1][b][c] += p[a][b][c] * pp;		
					ev[a - 1][b][c] += ev[a][b][c] * pp;		
				}
				if (b) {
					ld pp = (ld) b / (a + b + c);
					p[a + 1][b - 1][c] += p[a][b][c] * pp;	
					ev[a + 1][b - 1][c] += ev[a][b][c] * pp;	
				}
				if (c) {
					ld pp = (ld) c / (a + b + c);
					p[a][b + 1][c - 1] += p[a][b][c] * pp;
					ev[a][b + 1][c - 1] += ev[a][b][c] * pp;
				}
			}
		}
	}

	cout << setprecision(17) << fixed << ev[0][0][0] + cnt[1] + 2 * cnt[2] + 3 * cnt[3];
}

Measured memory_bytes: 428004
#include <bits/stdc++.h>
using namespace std;
int main()
{
  long long k,a,b;
  cin>>k>>a>>b;
  if(b-a<=2){
    cout<<k+1<<endl;
  }
  else{
    cout<<k+1+(b-a-2)*((k-a+1)/2)<<endl;
  }
  return 0;
}



Measured memory_bytes: 256
#include <iostream> // cin, cout, cerr
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota
#include <cstdio> // printf, scanf
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <iomanip> // cout<<setprecision(n)
#include <functional> // function<void(int)>
#include <cmath>
#include <cassert>
#include <bitset>

#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...)
#endif

#define int long long // at least int64 > 9*10^18
#define EL '\n'
#define rep(i,n) for(int i = 0; i < (n); i++)
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
using Graph = std::vector<std::vector<int> >;
const int INF = 1e17;
/* libraries */

signed main() {
	int n,m;
	std::cin >> n >> m;
	std::vector<int> a(m);
	rep(i,m) std::cin >> a[i];
	int sum=0;
	for(auto x:a) sum+=x;
	if(n<sum) print(-1);
	else print(n-sum);
	return 0;
}


Measured memory_bytes: 3684
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <algorithm>

using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, s, n) for (int i = (s); i <= (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
typedef long long ll;
typedef unsigned long long ull;

int main()
{
	int N;
	cin >> N;
	cout << N / 3 << endl;

	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        sc.nextLine();
        String S = sc.nextLine();
        sc.close();

        List<Integer> num = new ArrayList<Integer>();
        int obj = 1;
        int counter = 0;
        for (int i = 0; i < S.length(); i++) {
            if (S.charAt(i) == (char)('0' + obj)) {
                counter++;
            } else {
                num.add(counter);
                obj = 1 - obj;
                counter = 1;
            }
        }
        if (counter != 0) {
            num.add(counter);
        }
        if (num.size() % 2 == 0) {
            num.add(0);
        }

        int len = 2 * K + 1;
        int ans = 0;
        int temp;
        int sum[] = new int[num.size() + 1];
        sum[0] = 0;
        for (int i = 0; i < num.size(); i++) {
            sum[i + 1] = sum[i] + num.get(i);
        }
        for (int i = 0; i < num.size(); i += 2) {
            int left = i;
            int right = Math.min(i + len, sum.length - 1);
            temp = sum[right] - sum[left];
            ans = Math.max(ans, temp);
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 27332
/*
 * @Author: Luisvacson
 * @LastEditors: Luisvacson
 * @Descriptions: None
 * @Date: 2020-09-26 20:09:34
 * @LastEditTime: 2020-09-26 20:26:15
 * @FilePath: \VSC\C++\Practice\AC ACLBC C.cpp
 */
#include <bits/stdc++.h>
using namespace std;

int f[100005];
int find(int x)
{
    if (f[x] != x)
        f[x] = find(f[x]);
    return f[x];
}

void un(int x, int y)
{
    f[find(x)] = find(y);
}

int n, m;
bool vis[100005];
signed main()
{
    scanf("%d%d", &n, &m);
    register int i;

    for (i = 1; i <= n; ++i)
        f[i] = i;

    int x, y;
    for (i = 1; i <= m; ++i) {
        scanf("%d%d", &x, &y);
        un(x, y);
    }

    /*for (i = 1; i <= n; ++i)
        printf("%d ", f[i]);*/

    int ans = 0;
    for (i = 1; i <= n; ++i) {
        if (find(i) == i)
            ++ans;
    }

    printf("%d\n", ans - 1);
    return 0;
}

Measured memory_bytes: 4220