akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll,ll> P;
#define Mod 1000000007
using VP = vector<P>; using VVP = vector<VP>;
using VI = vector<ll>; using VVI = vector<VI>; using VVVI = vector<VVI>;
#define INF 1ll<<59

VVI w(2000,VI(2000,0));
ll s;

ll ww(ll a,ll b){
  if(a>=0&&b>=0) return w[a][b];
  else return 0;
}

ll solve(ll a,ll b,ll c, ll d){
  return ww(c,d)+ww(a,b)-ww(c,b)-ww(a,d);
}

int main(){
  ll i,j;
  ll n,k;
  cin>>n>>k;
  
  ll x,y;
  s=2*k;
  VVI v(s,VI(s,0));
  char c;
  for(i=0;i<n;i++){
    cin>>x>>y>>c;
    if(c=='B') x+=k;
    v[x%s][y%s]++;
  }
  for(j=0;j<s;j++) w[0][j]=v[0][j];

  for(i=1;i<s;i++) {
    for(j=0;j<s;j++){
      w[i][j]=w[i-1][j]+v[i][j];
    }
  }
  for(j=1;j<s;j++){
    for(i=0;i<s;i++){
      w[i][j]+=w[i][j-1];
    }
  }
  ll ans=0;
  for(i=0;i<k;i++){
    for(j=0;j<k;j++){
      ll temp=0;
      temp+=solve(-1,-1,i,j)+solve(i,j,i+k,j+k)+solve(i+k,-1,s-1,j);
      temp+=solve(-1,j+k,i,s-1)+solve(i+k,j+k,s-1,s-1);
      ans=max(ans,temp);
      ans=max(ans,n-temp);
    }
  }
  cout<<ans<<endl;

  return 0;
}

Measured memory_bytes: 62976
import java.util.Scanner;

public class Main {
	
	static int n;
	static int k;
	static int[] w;
	
	static boolean judge(int m) {
		int count = 1;
		int s = 0;
		for(int i=0;i<n;i++) {
			if(s+w[i] <= m) {
				s += w[i];
			}else {
				s = w[i];
				count++;
			}
		}
		if(count <= k) {
			return true;
		}else {
			return false;
		}
	}
	
	void main() {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		k = sc.nextInt();
		w = new int[n];
		int sum = 0;
		int max = 1;
		for(int i=0;i<n;i++) {
			w[i] = sc.nextInt();
			sum += w[i];
			max = Math.max(max, w[i]);
		}
		int l = Math.max(sum/n,max)-1;
		int h = 1000000000;
		while(l+1 < h) {
			int m = (l+h)/2;
			if(judge(m)) {
				h = m;
			}else {
				l = m;
			}
		}
		System.out.println(h);
	}
		
	public static void main(String[] args) {
		new Main().main();
	}
	
}


Measured memory_bytes: 71220
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pld pair<long double, int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define ff first
#define ss second
#define SZ(x) ((int)(x).size())
#define ld long double
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 1e3+100;
int H, W, sx, sy, x2, y2, D[MAXN][MAXN];
bool a[MAXN][MAXN], vis[MAXN][MAXN];

struct node{
    int x, y, d;
    bool operator<(const node &other) const{
        return d > other.d;
    }
};

bool valid(int x, int y){
    return (x >= 0 && x < H && y >= 0 && y < W && a[x][y]);
}

int dijkstra(){
    sx--, sy--, x2--, y2--;
    priority_queue<node> pq;
    pq.push({sx, sy, 0});
    D[sx][sy] = 0;
    while(!pq.empty()){
        int x = pq.top().x;
        int y = pq.top().y;
        int d = pq.top().d;
        pq.pop();
        if(vis[x][y])
            continue;
        vis[x][y] = true;
        for(int i = x-2; i <= x+2; i++){
            for(int j = y-2; j <= y+2; j++){
                if(!valid(i, j))
                    continue;
                if(i == x && j == y)
                    continue;
                if((i == x && abs(j - y) <= 1) || (j == y && abs(i - x) <= 1)){
                    if(D[i][j] > D[x][y]){
                        D[i][j] = D[x][y];
                        pq.push({i, j, D[i][j]});
                    }
                } else{
                    if(D[i][j] > D[x][y] + 1){
                        D[i][j] = D[x][y] + 1;
                        pq.push({i, j, D[i][j]});
                    }
                }
            }
        }
    }
    if(D[x2][y2] == INT_MAX)
        D[x2][y2] = -1;
    return D[x2][y2];
}

main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> H >> W;
    cin >> sx >> sy >> x2 >> y2;
    for(int i = 0; i < H; i++){
        string s; cin >> s;
        for(int j = 0; j < W; j++){
            a[i][j] = (s[j] == '.');
            D[i][j] = INT_MAX;
        }
    }
    cout << dijkstra();
}


Measured memory_bytes: 10196
#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cstdio>
#include<numeric>
using namespace std;
using ll = long long;
int main(){
  int s,w;
  cin >> s >> w;
  if(s > w){
    cout << "safe\n";
  }else{
    cout << "unsafe\n";
  }
  return 0;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

#define         pb         push_back
#define         sf(x)      scanf("%d",&x)
#define         sfl(x)     scanf("%lld",&x)
#define         pf(x)      printf("%d\n",x)
#define         pfl(x)     printf("%lld\n",x)
#define         endl       '\n'
#define         pii        pair<int,int>
#define         mapii      map<int,int>
#define         mapll      map<ll,ll>
#define         mapci      map<char,int>
#define         mapcl      map<char,ll>
#define         mapsi      map<string,int>
#define         mapsl      map<string,ll>
#define         pll        pair<ll,ll>
#define         vi         vector<int>
#define         vl         vector<ll>
#define         vd         vector<double,double>
#define         all(c)     c.begin(),c.end()
#define         F          first
#define         S          second
#define         mp         make_pair
#define        ftc(x)      cerr << #x << ": " << x << " " << endl;
#define         PI         acos(-1)
//   cout<<std::setprecision(12)<<

int main()
{
    double n;

    cin >> n;

    double l = n/3.00;

   cout<<std::setprecision(12)<<(l*l*l)<<endl;
}


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

const int INF = 2147483647;

typedef long long ll;

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;}

int main(){

    int N, W; cin >> N >> W;
    ll w, v;
    ll dp[N+1][W+1]; for(int i = 0; i <= N; i++){for(int j = 0; j <= W; j++){dp[i][j]=0;}}

    for(int i = 1; i <= N; i++){

        cin >> w >> v;

        for(int j = 1; j <= W; j++){
            if(j >= w){dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v);}
            else{dp[i][j] = dp[i-1][j];}
            //cout << "dp[" << i << "][" << j << "] = " << dp[i][j] << " "; 
        }
        //cout << endl;
    }

    cout << dp[N][W] << endl;
}

Measured memory_bytes: 79104
#D
import bisect
N,K,L = map(int,input().split())
PQ = [list(map(int,input().split())) for i in range(K)]
RS = [list(map(int,input().split())) for i in range(L)]

#UnionFind
class UF:
    def __init__(self,n):
        self.n = n
        self.root = [-1]*n #root[x]<0 ならxが根かつその値が木の要素数
        self.rank = [0]*n #木の深さ
    def __del__(self):
        pass
        
    def find(self,x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
            
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        
        if self.rank[x] < self.rank[y]:
            self.root[y] += self.root[x]
            self.root[x] = y
        else:
            self.root[x] += self.root[y]
            self.root[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x]+=1
                
    def same(self,x,y):
        return self.find(x) == self.find(y) #bool
    
    def count(self,x):
        return -self.root[self.find(x)]
    
uf1 = UF(N)
for pq in PQ:
    p,q = pq
    uf1.unite(p-1,q-1)
ar = [0]*N
uff1 = [uf1.find(i) for i in range(N)]
for i,u in enumerate(uff1):
    if u < 0:
        ar[i] = i
    else:
        ar[i] = u

uf2 = UF(N)
for rs in RS:
    r,s = rs
    uf2.unite(r-1,s-1)
br = [0]*N
uff2 = [uf2.find(i) for i in range(N)]
for i,u in enumerate(uff2):
    if u < 0:
        br[i] = i
    else:
        br[i] = u

cr = [[ar[i],br[i]] for i in range(N)]
dr = cr[::]
dr.sort()
for c in cr:
    ans = bisect.bisect_right(dr,c) - bisect.bisect_left(dr,c)
    print(ans,end=" ")


Measured memory_bytes: 87856
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
#define MOD 1000000007
#define INF 1e9
#define INFL 1e12
 
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
template<class T>void pr(T x){cout << x << endl;}
template<class T>void prvec(vector<T>& a){rep(i, a.size()-1){cout << a[i] << " ";} cout << a[a.size()-1] << endl;}
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; }

typedef pair<int, bool> edge;

int v, e;
vector<vector<edge>> G;
vector<int> ord, low;
set<int> ans;
vector<bool> seen;
int k;
int zero_degree;

void dfs(int u){
    // pr(u);
    seen[u] = true;
    ord[u] = k; k++;
    low[u] = ord[u];
    for(edge &ed: G[u]){
        int v = ed.first;
        if(!seen[v]){
            ed.second = true;
            dfs(v);
            chmin(low[u], low[v]);
            if(u!=0 && ord[u] <= low[v] && ans.find(u)==ans.end()){
                // printf("(%d %d) is pushed\n", u, v);
                ans.insert(u);
            }
            // printf("(%d: %d %d) ",u, ord[u], low[u]);
            // printf("(%d %d)", ord[u], low[u]);
        }else if(ed.second==false){
            // if(ord[u]==low[v]) continue;
            chmin(low[u], ord[v]);
        }
    }
    // printf("(%d: %d %d) ",u, ord[u], low[u]);
}
 
int main()
{
    cin >> v >> e;
    // cout << v << " " << e << endl;
    G.resize(v); ord.resize(v), low.resize(v); seen.resize(v);

    int a, b;
    rep(i, e){
        cin >> a >> b;
        G[a].push_back({b, false});
        G[b].push_back({a, false});
    }
    // cout << G.size();
    // rep(i, v){
    //     for(auto ed: G[i]){
    //         printf("(%d %d) ", i, ed.first);
    //     }
    //     printf("\n");
    // }
    rep(i, v) seen[i]=false;
    int k = 0;

    dfs(0);

    // cout << endl;
    // rep(i, v){
    //     printf("(%d: %d %d) ",i, ord[i], low[i]);
    // }
    // cout << ans.size() << endl;
    int tmp=0;
    // printf("\n");
    for(edge ed: G[0]){
        // printf("%d\n", ed.second);
        if(ed.second) tmp++;
    }
    if(tmp>1) ans.insert(0);

    for(int i: ans){
        pr(i);
    }
    return 0;
}


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

// types
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;

// macros
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int mod = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  ll n;
  cin >> n;

  vector<ll> a(n);
  REP(i, n)
    cin >> a[i];

  vector<pll> max_e(2, make_pair(0,0));

  REP(i, n){
    if(max_e[0].FI <= a[i]){
      max_e[1].FI = max_e[0].FI;
      max_e[1].SE = max_e[0].SE;

      max_e[0].FI = a[i];
      max_e[0].SE = i;
    }
    else if(max_e[1].FI <= a[i]){
      max_e[1].FI = a[i];
      max_e[1].SE = i;
    }

  }

  REP(i, n){
    if(i ==  max_e[0].SE)
      cout << max_e[1].FI << endl;
    else
      cout << max_e[0].FI << endl;
  }

  
}


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

using namespace std;
typedef long long ll;

#define REP(i, n) for (ll i = 0; i < (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 FORR(i, m, n) for (ll i = (m); i >= (n); i--)
#define INF 1e9
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((ll)(x).size())
#define SORT(x) sort((x).begin(), (x).end())
#define dump(x) cerr << #x << " = " << (x) << endl
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
                      << " " << __FILE__ << endl

int main(int argc, char const *argv[])
{
    ll n;
    cin >> n;
    for (ll i = 1;; i++)
    {
        if (i * i > n)
        {
            cout << (i - 1) * (i - 1) << endl;
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 764
n = int(input())

a = list(map(int,input().split()))

b = {}

for i in a:
    if i in b:
        b[i] += 1
    else:
        b[i] = 1
ans = 0
for i in b:
    if i < b[i]:
        ans += b[i]-i
    elif i > b[i]:
        ans += b[i]
print(ans)

Measured memory_bytes: 18164
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>

using namespace std;
using LLONG = long long;
const LLONG MOD = 998244353;

int main()
{
    LLONG A, B, C, K;
    cin >> A >> B >> C >> K;
    // K回の操作後，高橋君の数から中橋君の数を引くと
    // (-1)^K*(A-B)となる
    LLONG ans = K % 2 == 0 ? A - B : B - A;
    if (abs(ans) > 1e18)
    {
        cout << "Unfair" << endl;
    }
    else
    {
        cout << ans << endl;
    }
}


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

int main() {
  int n, k; cin >> n >> k;
  int x[100001] = {};
  for (int i = 1; i <= n; i++) cin >> x[i];

  int cost = INT_MAX;
  for (int i = 1; i <= n - k + 1; i++) {
    int cost1 = abs(x[i]) + abs(x[i+k-1]-x[i]);
    int cost2 = abs(x[i+k-1]) + abs(x[i]-x[i+k-1]);
    cost = min(cost, min(cost1, cost2));
  }
  cout << cost << endl;
}

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

using namespace std;

const int MAX_POS = 1e4 + 10, MAX_SUM = 110, MOD = 1e9 + 7;

inline void add (int& a, int b) { a = (a + b) % MOD; }

string K;
int D;
int memo[MAX_POS][MAX_SUM][2];

int dp (int pos, int sum, int lt) {
  if (pos == int(K.size())) return sum == 0;
  int& ret = memo[pos][sum][lt];
  if (~ret) return ret;
  ret = 0;
  if (lt) {
    for (int d = 0; d <= 9; d++) {
      add(ret, dp(pos + 1, (sum + d) % D, lt));
    }
  }
  else {
    for (int d = 0; d <= K[pos]; d++) {
      add(ret, dp(pos + 1, (sum + d) % D, d < K[pos]));
    }
  }
  return ret;
}

int main () {
  cin >> K >> D;
  for (char& ch: K) ch -= '0';
  memset(memo, -1, sizeof memo);
  cout << (dp(0, 0, 0) + MOD - 1) % MOD << endl;
  return (0);
}


Measured memory_bytes: 9600
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    // TODO 自動生成されたメソッド・スタブ

    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int a[] = new int[n];

    for (int i = 0; i < n; i++) {
      a[i] = sc.nextInt();
    }

    int min = a[0];
    for (int i = 1; i < n; i++) {
      min = Math.min(min, minValue(a[i], a[i - 1]));
    }

    System.out.println(min);
  }

  public static int minValue(int a, int b) {
    if (a == b) {
      return a;
    }
    if (a > b) {
      a = a % b;
      if (a == 0) {
        return b;
      }
    } else {
      b = b % a;
      if (b == 0) {
        return a;
      }
    }

    return minValue(a, b);
  }
}


Measured memory_bytes: 50200
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod 			1000000007
#define tc(t) 			int t;cin >> t;while(t--)
#define for0(i , n)		for(int i=0;i<n;i++)
#define loop(i , a, b)	for(int i=a;i<=b;i++)
#define endl 			'\n'
#define inf 			1e18
#define fi 				first
#define se 				second

int XX[8] = { +1, +1, +1, 0, 0, -1, -1, -1};
int YY[8] = { +1, 0, -1, +1, -1, +1, 0, -1};
int dx[4] = { -1, 1, 0, 0};
int dy[4] = {0, 0, 1, -1};

vector<vector<int>> multiply(vector<vector<int>> A, vector<vector<int>> B) {
	int n = A.size();
	vector<vector<int>> res(n, vector<int>(n, 0));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int x = 0; x < n; x++) {
				res[i][j] = (res[i][j] + A[i][x] * B[x][j]) % mod;
			}
		}
	}

	return res;
}

vector<vector<int>> power(vector<vector<int>> mat, int exp) {
	if (exp == 1) return mat;
	vector<vector<int>> res = power(mat, exp / 2);
	if (exp & 1)
		return multiply(multiply(mat, res), res);
	return multiply(res, res);
}

signed main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

#ifndef ONLINE_JUDGE
	freopen("input.txt" , "r" , stdin);
	freopen("output.txt" , "w" , stdout);
#endif

	int n, k;
	cin >> n >> k;

	vector<vector<int>> a(n, vector<int>(n, 0));

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

	vector<vector<int>> ak = power(a, k);
	int ans = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			ans = (ans + ak[i][j]) % mod;
		}
	}

	cout << ans << endl;

	return 0;
}

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

using namespace std;

#define ll long long

void solve() {
	string s;
  	cin >> s;
  	int cnt = 0;
  	for (int i = 0; i < s.length(); i++) {
    	if (s[i] == '1') {
			cnt++;
        }
    }
	cout << cnt << "\n";
}

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

	int t = 1, i = 1;
	//cin >> t;
	while(t--) {
		//cout << "Case #" << i << ": ";
		solve();
		//i++;
	}
	return 0;
}



Measured memory_bytes: 3612
#include <iostream>
#include <math.h>
//#include <numeric>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;
#define n_max 100000
#define N_max 100

#define rep(i, a, n) for(int i = a; i < n; i++)
#define lrep(i, a, n) for(long int i = a; i < n; i++)
#define in(a) cin >> a
#define out(a) cout << a << endl

int main()
{
    int N;
    int A[n_max];

    cin >> N;

    for(int i = 0; i < N; i++) {
        cin >> A[i]; 
    }        
   
    int index = 0;
    int ans = 0;
    while(index < N) {
        int cnt_upper = 0;
        int cnt_lower = 0;
        bool pre_upper = true;
        bool pre_lower = true;
        for(int i = index; i < N -1; i++) {

            if((A[i] <= A[i+1]) && pre_upper) { cnt_upper++; }
            else { pre_upper = false;}

            if((A[i+1] <= A[i]) && pre_lower) { cnt_lower++; }
            else { pre_lower = false;}
            
            if(!pre_upper && !pre_lower) break;
        }
        index += (max(cnt_upper, cnt_lower) + 1);  
        ans++;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define uli unsigned long long int
#define INF 999999999999999999
#define rep(i,m,n) for(lli i = m;i < n;i++)
#define rrep(i,m,n) for(lli i=m-1;i>=n;i--)
#define pb(n) push_back(n)
#define UE(N) N.erase(unique(N.begin(),N.end()),N.end());
#define Sort(n) sort(n.begin(), n.end())
#define Rev(n) reverse(n.begin(),n.end())
#define Out(S) cout << S << endl
#define NeOut(S) cout << S
#define HpOut(S) cout << setprecision(25) << S << endl
#define Vec(K,L,N,S) vector<L> K(N,S)
#define DV(K,L,N,M,S) vector<vector<L>> K(N,vector<L>(M,S))
#define TV(K,L,N,M,R,S) vector<vector<vector<L>>> K(N,vector<vector<L>>(M,vector<L>(R,S)))
#define pint pair<lli,lli>
#define paf(L,R) pair<L,R>
#define mod 1000000007
#define MAX 510000
#define ALL(a)  a.begin(),a.end()
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
lli gcd(lli num1, lli num2){
    return num2 != 0 ? gcd(num2, num1 % num2) : num1;
}
lli lcm(lli num1, lli num2){
    return num1 / gcd(num1, num2) * num2;
}
lli repow(lli n,lli k,lli m){
  if(k==0)return 1;
  else if(k%2==1)return repow(n,k-1,m)*n%m;
  else{
    lli temp=repow(n,k/2,m);
    return temp*temp%m;
  }
}
map<lli,int>prime_factor(lli n){
  map<lli,int>res;
  for(lli i=2;i*i<=n;i++){
    while(n%i==0){
      res[i]++;
      n/=i;
    }
  }
  if(n!=1)res[n]=1;
  return res;
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  lli A,B,C,D,E,F,N,M,K,L,X,Y,Z,H,W,sum=0,num=0,flag=0;string S,T;
  cin >> A >> B;
  Out(prime_factor(gcd(A,B)).size()+1);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const ll inf = (1 << 30) - 1;
const ll infll = (1LL << 61) - 1;

char s[9][5] = {{'.', ',', '!', '?', ' '},
                {'a', 'b', 'c'},
                {'d', 'e', 'f'},
                {'g', 'h', 'i'},
                {'j', 'k', 'l'},
                {'m', 'n', 'o'},
                {'p', 'q', 'r', 's'},
                {'t', 'u', 'v'},
                {'w', 'x', 'y', 'z'}};

map<char, int> mp;
int N;

int main()
{
    cin >> N;
    for (int i = 1; i <= 9; i++)
    {
        char c = i + '0';
        if (i == 1)
            mp[c] = 5;
        else if (i == 9 || i == 7)
            mp[c] = 4;
        else
            mp[c] = 3;
    }
    for (int i = 0; i < N; i++)
    {
        string t;
        cin >> t;
        int cnt = 0, n = t.size();
        char now = t[0];
        for (int j = 1; j < n; j++)
        {
            if (t[j] == now)
                cnt++;
            else
            {
                if (now != '0')
                {
                    cnt %= mp[now];
                    cout << s[now - '1'][cnt];
                }
                now = t[j], cnt = 0;
            }
        }
        cout << endl;
    }
}


Measured memory_bytes: 3076
#include <bits/stdc++.h>
using namespace std;
int main () {
    int ans = 0;
    string S;
    cin >> S;
    for (int i = 0, j = S.length() - 1; i < j; i++, j--) {
        if (S[i] != S[j]) {
            ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<cstdio>
#include<unordered_map>
using namespace std;
//---------------------------------------------------
//ライブラリゾーン！！！！
typedef long long ll;
typedef long double ld;
#define str string
#define rep(i,j) for(ll i=0;i<(long long)(j);i++)
const ll Mod = 1000000007;
const ll gosenchou = 5000000000000000;
short gh[2][4] = { { 0,0,-1,1 },{ -1,1,0,0 } };
struct P {
	ll pos, cost;
};
bool operator<(P a, P b) { return a.cost < b.cost; }
bool operator>(P a, P b) { return a.cost > b.cost; }
struct B {//隣接リスト表現
	ll to, cost;
};
struct E {//辺の情報を入れる変数
	ll from, to, cost;
};
bool operator<(E a, E b) {
	return a.cost < b.cost;
}
struct H {
	ll x, y;
};
bool operator<(H a, H b) {
	if (a.x != b.x) return a.x < b.x;
	return a.y < b.y;
}
bool operator>(H a, H b) {
	if (a.x != b.x) return a.x > b.x;
	return a.y > b.y;
}
bool operator==(H a, H b) {
	return a.x == b.x&&a.y == b.y;
}
bool operator!=(H a, H b) {
	return a.x != b.x || a.y != b.y;
}
ll gcm(ll i, ll j) {//最大公約数
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcm(j%i, i);
}
ld rad(H a, H b) {
	return sqrt(pow(a.x - b.x, 2.0) + pow(a.y - b.y, 2.0));
}//rad＝座標上の2点間の距離
ll ari(ll a, ll b, ll c) {
	return (a + b)*c / 2;
}//等差数列の和
bool suf(ld a, ld b, ld c, ld d) {
	if (b <= c || d <= a) return 0;
	return 1;
}//[a,b),[c,d)
ll fact(ll i) {
	ll sum = 1;
	for (ll j = 2; j <= i; j++)
		sum = (sum* j) % Mod;
	return sum;
}//階乗(正）
#define int long long
const long long inf = 4523372036854775807;
const int iinf = 1500000000;
//---------------------------------------------------
//+++++++++++++++++++++++++++++++++++++++++++++++++++
signed main() {
	int a, b;
	string s;
	cin >> a >> b >> s;
	for (int i = 0; i < a; i++) {
		if (!(s[i] <= '9'&&s[i] >= '0')) {
			cout << "No\n";
			return 0;
		}
	}
	if (s[a] != '-') {
		cout << "No\n";
		return 0;
	}
	for (int i = a+1; i < s.size(); i++) {
		if (!(s[i] <= '9'&&s[i] >= '0')) {
			cout << "No\n";
			return 0;
		}
	}
	cout << "Yes\n";
	getchar(); getchar();
}

Measured memory_bytes: 256
#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include <prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

template <typename T>
void print(T x) {
    cout << x << "\n";
}

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, m, n) for (ll i = (m); i < (n); ++i)
#define REVFOR(i, m, n) for (ll i = (n - 1); i >= (m); --i)
#define REP(i, n) FOR(i, 0, n)
#define REVREP(i, n) REVFOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

//const ll MOD = 998244353;
struct mint {
    ll x; // typedef long long ll;
    mint(ll x=0):x((x%MOD+MOD)%MOD){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += MOD-a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    mint operator+(const mint a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    // for prime MOD
    mint inv() const {
        return pow(MOD-2);
    }
    mint& operator/=(const mint a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint a) const {
        return mint(*this) /= a;
    }
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    int n, m; cin >> n >> m;

    if (abs(n - m) > 1) {
        print(0);
        return 0;
    }

    mint ans = 1;
    FOR(i, 1, n+1) ans *= i;
    FOR(i, 1, m+1) ans *= i;

    if (n == m) ans *= 2;

    print(ans);
}

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

int main(){
    int flag=0;
    int x,p,fx=0;
    int ans;

    cin >>x;
    p=x;
    while (p>0){
        fx += (p%10);
        p /= 10;
    }
    
    if(x%fx==0)flag=1;
    //cout << ans <<endl;
    //cout <<fixed<<setprecision(16)<< ans <<endl;

    if(flag==1)cout << "Yes" <<endl;
    else cout << "No" <<endl;
    
    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);
        double r = sc.nextDouble();
        double pi = Math.PI;
        double L = 2.0 * r * pi;
            double S = r * r * pi;

            System.out.printf("%.6f " , S);
            System.out.printf("%.6f\n" , L);
    }
}


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

#define MAX_N 100000

int N, L, Q;
int x[MAX_N];
int tab[20][MAX_N];

// mid日でaからbまで行けるか
bool C(int a, int b, int mid){
	int pos = a;
	int cnt = 0;
	while(mid != 0){
		if(mid & 1){
			pos = tab[cnt][pos];
		}
		mid >>= 1;
		cnt++;
	}
	if(pos >= b) return true;
	else return false;
}


int solve(int a, int b){
	if(a > b) swap(a, b);

	int ub = 100000;
	int lb = 0;
	while(ub - lb > 1){
		int mid = lb + (ub - lb) / 2;
		if(C(a, b, mid)) ub = mid;
		else lb = mid;
	}
	return ub;
}

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

	cin >> N;
	for(int i=0; i<N; i++) cin >> x[i];
	cin >> L >> Q;

	for(int i=0; i<N; i++){
		tab[0][i]  = upper_bound(x, x+N, x[i]+L) - x - 1;
	}

	for(int k=0; k<19; k++){
		for(int i=0; i<N; i++){
			tab[k+1][i] = tab[k][min(N-1, tab[k][i])];
		}
	}

	for(int i=0; i<Q; i++){
		int a, b;
		cin >> a >> b;
		a--; b--;
		cout << solve(a, b) << endl;
	}

	return 0;
}


Measured memory_bytes: 9088
#include <iostream>
#include <algorithm>
#include <string>
#include <stack>
#include <map>
#include <queue>
#include <vector>
using namespace std;

int main() {
	int i, x, n, pri, start;
	long long int sum;
	pri = 1;
	sum = 0;
	cin >> n;
	vector<int> mon(n);
	for (i = 0; i < n; i++) {
		cin >> mon[i];
	}
	for (i = 0; i < n; i++) {
		if (mon[i] == pri) {
			pri++;
		}
		else if (mon[i] > pri) {
			sum += (mon[i] - 1) / pri;
			mon[i] = (mon[i] - 1) % pri + 1;
			pri = max(pri, 2);
		}
	}
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 768
s = input()
t = int(input())
v = set(s)

ans = 0
if len(v) == 1:
  ans = (len(s)*t)//2
  print (ans)
  exit()

a = []
o = s[0]
c = 0

for i in range(len(s)):
  if o == s[i]:
    c += 1
  else:
    a.append([o,c])
    c = 1
    o = s[i]
a.append([o,c])

for i,j in a:
  if j == 1:
    continue
  ans += (j//2)*t

if len(v) > 1:
  if a[0][0] == a[-1][0]:
    if a[0][1]%2 == 1 and a[-1][1]%2 == 1:
      ans += t-1

print (ans)

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

namespace atCocderCs
{
    class Program
    {

        static void Main(string[] args)
        {
            string[] vals = Console.ReadLine().Split(' ');
            int ab = Convert.ToInt32( vals[0] + vals[1]);
            int r = Convert.ToInt32(Math.Sqrt(ab));

            if (r * r == ab)
                Console.WriteLine("Yes");
            else
                Console.WriteLine("No");
            
        }

    }
}


Measured memory_bytes: 13268
#define _USE_MATH_DEFINES
#include <iostream>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>
#include <cfloat>
#include <map>
#include <set>
#include <array>
#include <stdio.h>
#include <string.h>
#include <random>
using ll = long long;
using ull = unsigned long long;
using namespace std;
#define int long long
#define CONTAINS_VEC(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define REMOVE(v,a) (v.erase(remove((v).begin(), (v).end(), (a)), (v).end()))
#define REVERSE(v) (reverse((v).begin(), (v).end()))
#define ARY_REVERSE(v,a) (reverse((v), (v)+(a)))
#define REP(i, n) for (int (i)=0; (i) < (n); (i)++)
#define CONTAINS_MAP(m, a) (m).find((a)) != m.end()
#define CONTAINS_SET(m, a) (m).find((a)) != m.end()
void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; }

int N;
vector<int> link[100001];
map<int, int> ans[100001];
int A[100001];
int B[100001];
int _max = 1;

void func(int n, int from, int parent)
{
	int cur = 1;
	if (parent == cur) cur++;

	for (int l : link[n])
	{
		if (l != from)
		{
			ans[n][l] = cur;
			ans[l][n] = cur;

			func(l, n, cur);
			_max = max(_max, cur);

			cur++;
			if (parent == cur) cur++;
		}
	}
}

signed main()
{
	cin >> N;
	REP(i, N - 1)
	{
		int a, b;
		cin >> a >> b;
		A[i] = a;
		B[i] = b;
		link[a].push_back(b);
		link[b].push_back(a);
	}

	func(1, -1, -1);

	cout << _max << endl;
	REP(i, N - 1)
	{
		int n = ans[A[i]][B[i]];
		cout << n << endl;
	}
}



Measured memory_bytes: 25496
let w=read_int()and n=read_int()open Array;;let z=init w(fun i->i+1);;let rec f i=if i=n then iter(fun e->Printf.printf"%d
"e)z else Scanf.scanf"%d,%d
"(fun a b->let t=z.(a-1)in z.(a-1)<-z.(b-1);z.(b-1)<-t;f(i+1));;f 0

Measured memory_bytes: 2220
input = input().split()
# inputList = list(input[0])

a = int(input[0])
b = int(input[1])
# c = int(input[2])

# inputList.sort()

if a < b:
    print(0)
else:
    print(10)



# flg = 1
# for i in range(0, len(inputList)-1):
#     if inputList[i] == inputList[i + 1]:
#         flg = 0
#         break
#
# if flg == 0:
#     print("Bad")
# else:
#     print("Good")


Measured memory_bytes: 38256
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;

const int maxn = 1e5 + 5;
int dp[maxn];
int stn[maxn];

int main(){
	int n,i;
	scanf("%d",&n);
	for(i = 1; i <= n; i++) scanf("%d",&stn[i]);
	dp[1] = 0;
	dp[2] = abs(stn[2] - stn[1]);
	
	for(i = 3; i <= n; i++){
		dp[i] = min(dp[i - 1] + abs(stn[i - 1] - stn[i])  ,  dp[i - 2] + abs(stn[i - 2] - stn[i]));
	}

	int ans = dp[n];
	printf("%d\n",dp[n]);

	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(std::unique(all(x)), x.end());
typedef long long ll;
const int INF = 1e9;
const ll MOD = 1e9+7;
const ll LINF = 1e18;
const double PI=acos(-1);
using namespace std;
vector<int> dx={1,0,-1,0};
vector<int> dy={0,1,0,-1};
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; }
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

int main() {
    int n;
    cin>>n;
    int k=-1;
    for(int i = 0; i < 500; i++) {
        if(i*(i+1)/2==n) {
            k=i;
        }
    }
    if(k==-1) {
        cout<<"No"<<endl;
        return 0;
    }

    auto vec=make_vec<int>(k,k);
    int now=1;
    for(int i = 0; i < k; i++) {
        for(int j = 0; j <= i; j++) {
            vec[i][j]=now;
            vec[j][i]=now;
            now++;
        }
    }   

    cout<<"Yes"<<endl;
    cout<<k+1<<endl;
    for(int i = 0; i < k; i++) {
        cout<<k<<" ";
        for(int j = 0; j < k; j++) {
            cout<<vec[i][j]<<" \n"[j==k-1];
        }
    }
    cout<<k<<" ";
    for(int i = 1; i <= k; i++) {
        cout<<i*(i+1)/2<<" \n"[i==k];
    }
}



Measured memory_bytes: 2176
#include <iostream>
#include <vector>
#include <set>
#include <cmath>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> v(n+1);
    for(int i = 0; i <= n; ++i)
    {
        cin >> v[i+1];
    }

    vector<set<int>> measure(n+1);
    for(int i = 1; i <= sqrt(n); ++i)
    {
        for(int j = 1; i*j <= n; ++j)
        {
            measure[i*j].insert(j);
            measure[i*j].insert(i);
        }
    }

    vector<int> ans;
    vector<int> memo(n+1);
    int cnt = 0;
    for(int i = n; i > 0; --i)
    {
        if((v[i] % 2) != (memo[i] % 2))
        {
            ans.push_back(i);
            ++cnt;
            for(int idx : measure[i])
            {
                memo[idx] += 1;
            }
        }
    }
    cout << ans.size() << endl;
    bool first = true;
    for(int num : ans)
    {
        if(!first)
        {
            cout << " ";
        }
        else
        {
            first = false;
        }
        cout << num;
    }
    cout << endl;
}

Measured memory_bytes: 128248
import bisect
from operator import itemgetter

n,m=map(int,input().split())
a=list(map(int,input().split()))
bc=[tuple(map(int,input().split())) for i in range(m)]

a.sort()
bc.sort(key=itemgetter(1), reverse=True)

ans=0
for i in range(m):
  b=bc[i][0]
  c=bc[i][1]
  ika=bisect.bisect_left(a, c)
  if ika<=b:
    ans+=ika*c
    del a[:ika]
  else:
    ans+=b*c
    del a[:b]
  #print(ika,a)

ans+=sum(a)
print(ans)

Measured memory_bytes: 23780
#include <bits/stdc++.h>
using namespace std;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ll long long
#define ld long double
#define all(a) (a).begin(),(a).end()
#define mk make_pair
ll MOD=1000000007;
int inf=1000001000;
ll INF=100000000000000000;

template< unsigned mod >
struct RollingHash {
  vector< unsigned > hashed, power;

  inline unsigned mul(unsigned a, unsigned b) const {
    unsigned long long x = (unsigned long long) a * b;
    unsigned xh = (unsigned) (x >> 32), xl = (unsigned) x, d, m;
    asm("divl %4; \n\t" : "=a" (d), "=d" (m) : "d" (xh), "a" (xl), "r" (mod));
    return m;
  }

  RollingHash(const string &s, unsigned base = 10007) {
    int sz = (int) s.size();
    hashed.assign(sz + 1, 0);
    power.assign(sz + 1, 0);
    power[0] = 1;
    for(int i = 0; i < sz; i++) {
      power[i + 1] = mul(power[i], base);
      hashed[i + 1] = mul(hashed[i], base) + s[i];
      if(hashed[i + 1] >= mod) hashed[i + 1] -= mod;
    }
  }

  unsigned get(int l, int r) const {
    unsigned ret = hashed[r] + mod - mul(hashed[l], power[r - l]);
    if(ret >= mod) ret -= mod;
    return ret;
  }

  unsigned connect(unsigned h1, int h2, int h2len) const {
    unsigned ret = mul(h1, power[h2len]) + h2;
    if(ret >= mod) ret -= mod;
    return ret;
  }

  int LCP(const RollingHash< mod > &b, int l1, int r1, int l2, int r2) {
    int len = min(r1 - l1, r2 - l2);
    int low = -1, high = len + 1;
    while(high - low > 1) {
      int mid = (low + high) / 2;
      if(get(l1, l1 + mid) == b.get(l2, l2 + mid)) low = mid;
      else high = mid;
    }
    return (low);
  }
};

using RH = RollingHash< 1000000007 >;
//get(l,r)�͋��[l,r)�̃n�b�V���l�����߂�

int main() {
    int n;
    string s;
    cin >> n >> s;
    int ans=0;
    RH rh(s);
    rep(i,n-1){
        for (int j=i+1+ans;j<n;j++){
            if (j+ans>=n) break;
            if (s.at(i+ans)!=s.at(j+ans)) continue;
            if (rh.get(i,i+ans)==rh.get(j,j+ans)){
            while(true){
                if (i+ans==j) break;
                if (j+ans>=n) break;
                if (s.at(i+ans)!=s.at(j+ans)) break;
                ans++;
            }
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define simplify ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define endl "\n"
using namespace std;


int32_t main() {

    simplify
    int n;
    cin>>n;

    int ans=n%1000==0?0:1000-n%1000;
    cout<<ans<<endl;
    

    return 0;
}



Measured memory_bytes: 3652
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
book_a = [0] * (n + 1)
book_b = [0] * (m + 1)

for i in range(n):
    book_a[i+1] = book_a[i] + a[i]

for j in range(m):
    book_b[j + 1] = book_b[j] + b[j]

r = m
ans = 0

for i in range(n + 1):
    if book_a[i] > k:
        break
    while book_a[i] + book_b[r] > k:
        r -= 1
    ans = max(ans, i + r)

print(ans)


Measured memory_bytes: 47324
#include <algorithm>
#include <cfloat>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define ll long long
#define eps LDBL_EPSILON
#define mod 1000000007
#define int long long
#define double long double
#define INF INT_MAX
#define P pair<int,int>
#define prique priority_queue
using namespace std;
int n, g[2][3];
int dp[4][25000010];
inline int mymax(int a, int b) {
	return a > b ? a : b;
}
signed main() {
	cin >> n;
	rep(i, 2) {
		rep(j, 3)cin >> g[i][j];
	}
	rep(i, 3) {
		rep(j, n + 1) {
			if (!i)dp[i][j] = n - j;
			if (j < g[0][i])dp[i + 1][j] = mymax(dp[i][j], dp[i + 1][j - 1] - 1);
			else dp[i + 1][j] = mymax(mymax(dp[i][j], dp[i + 1][j - g[0][i]] + g[1][i] - g[0][i]), dp[i + 1][j - 1] - 1);
		}
	}
	rep(j, n + 1)n = max(n, dp[3][j]);
	dp[0][0] = n;
	rep(i, 3) {
		rep(j, n + 1) {
			if (!i)dp[i][j] = n - j;
			if (j < g[1][i])dp[i + 1][j] = mymax(dp[i][j], dp[i + 1][j - 1] - 1);
			else dp[i + 1][j] = mymax(mymax(dp[i][j], dp[i + 1][j - g[1][i]] + g[0][i] - g[1][i]), dp[i + 1][j - 1] - 1);
		}
	}
	int ans = 0;
	rep(j, n + 1)ans = max(ans, dp[3][j]);
	cout << ans << endl;
}

Measured memory_bytes: 781440
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;
using P = pair<int, int>;
constexpr ld EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr int MOD = 1e9 + 7;

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

    int n, d;
    while (cin >> n >> d, n || d)
    {
        vector<int> sum(n, 0);
        vector<stack<int>> st(n);
        for (int i = 0; i < n; i++)
        {
            int m;
            cin >> m;
            for (int j = 0; j < m; j++)
            {
                int c;
                cin >> c;
                sum[i] += c;
                st[i].push(c);
            }
        }
        while (true)
        {
            bool update = false;
            for (int i = 0; i < n; i++)
            {
                if (st[i].empty())
                    continue;
                int mi = sum[i] - st[i].top(), ma = mi;
                for (int j = 0; j < n; j++)
                {
                    if (i == j)
                        continue;
                    mi = min(mi, sum[j]);
                    ma = max(ma, sum[j]);
                }
                if (ma - mi > d)
                    continue;
                sum[i] -= st[i].top();
                st[i].pop();
                update = true;
                break;
            }
            if (!update)
                break;
        }
        bool f = true;
        for (int i = 0; i < n; i++)
            if (!st[i].empty())
                f = false;
        if (f)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
}



Measured memory_bytes: 3096
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  
  if (a+b >c+d){
    cout << "Left" <<endl;
  }
  else if(a+b < c+d){
    cout << "Right" << endl;
  }
  else{
    cout << "Balanced"<<endl;
  }
}
 


Measured memory_bytes: 256
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

s = input()
k = INT()
a = set()
for i in range(len(s)):
    t = s[i]
    a.add(t)
    if i < len(s) - 1:
        for j in range(i+1, min(i+k+1,len(s))):
            t += s[j]
            a.add(t)
b = sorted(list(a))
print(b[k-1])

Measured memory_bytes: 13912
#include <bits/stdc++.h>
using namespace std;
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

#define INF 2147483600
#define long long long

int main(){
  int n;
  cin>>n;
  vector<pair<long, long>> vec(n);
  rep(i,n){
    long d;
    cin>>d;
    vec[i] = mp(d,i);
  }

  sort(all(vec), greater<pair<long,long>>());
  vec.pb(mp(0,0));

  vector<long> ans(n, 0LL);
  long i=0;
  int m = INF;
  while(i<n){
    while(i<n && vec[i].fi==vec[i+1].fi) i++;
    m = min<int>(m, vec[i].se);
    ans[m] += (i+1)*(vec[i].fi-vec[i+1].fi);
    i++;
  }

  rep(i,n) cout<<ans[i]<<endl;

  return 0;
}


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

const int N = 1e5 + 10;

int a[N];

int main(){
	int n;
	long long ans;
	scanf("%d",&n);
	for (int i = 1; i <= n; i++) scanf("%d",&a[i]);
	ans = 0;
	for (int i = 1; i <= n; i++){
		ans += a[i] / 2;
		a[i] %= 2;
		if (i < n && a[i] > 0 && a[i + 1] > 0){
			a[i]--;
			a[i + 1]--;
			ans++;
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include<sstream>
#include<vector>
#include<iterator>
#include<queue>
#include<utility>
#include<functional>
#include<set>
using namespace std;

double calcConcentration(int water, int sugar)
{
	if(water == 0 && sugar == 0)
		return 0.0;

	return 100.0 * sugar / (sugar + water);
}

int main(void)
{
	int A, B, C, D, E, F;
	cin >> A >> B >> C >> D >> E >> F;

	vector<int> sugar(4, 0), water(4, 0);
	water[0] = 100 * A;
	water[1] = 100 * B;
	sugar[2] = C;
	sugar[3] = D;

	typedef pair<int, int> State;
	priority_queue<State, vector<State>, greater<State>> task;
	set<State> table;

	State seed = make_pair(water[0], 0);
	task.push(seed);
	table.insert(seed);
	seed = make_pair(water[1], 0);
	task.push(seed);
	table.insert(seed);

	 State ret = make_pair(water[0], 0);
	while(task.empty() != true)
	{
		auto sw = task.top();
		task.pop();

		for(int i=0; i<4; i++)
		{
			int nextWater = sw.first + water[i];
			int nextSugar = sw.second + sugar[i];

			if((nextWater+nextSugar > F) || (nextSugar > nextWater*E/100))
				continue;

			auto next = make_pair(nextWater, nextSugar);
			if(table.find(next) != table.end())
				continue;

			if(calcConcentration(next.first, next.second) > calcConcentration(ret.first, ret.second))
				ret = next;

			task.push(next);
			table.insert(next);
		}
	}

	cout << ret.first+ret.second << " " << ret.second << endl;

	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#ifdef ENABLE_DEBUG_OUTPUT
#define DEBUG_LOG(s) cout << s << endl;
#else
#define DEBUG_LOG(s) void();
#endif

double calcAngle(double h, double m)
{
    // validate the input
    if (h <0 || m < 0 || h >12 || m > 60)
        printf("Wrong input");

    if (h == 12) h = 0;
    if (m == 60) m = 0;

    // Calculate the angles moved
    // by hour and minute hands
    // with reference to 12:00
    double hour_angle = 0.5 * (h * 60 + m);
    double minute_angle = 6 * m;

    // Find the difference between two angles
    double angle = abs(hour_angle - minute_angle);

    // Return the smaller angle of two possible angles
    angle = min(360 - angle, angle);

    return angle;
}

int main(){
    double a, b, h, m;
    cin >> a >> b >> h >> m;

    double p = calcAngle(h, m);
    p = p * M_PI / 180;
    // cout << p << " " << cos(p) << endl;
    double c = sqrt(pow(a, 2) + pow(b, 2) - 2 * a * b * cos(p));

    cout << fixed << setprecision(20) << c << endl;
    return 0;
}

Measured memory_bytes: 4056