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

using namespace std;

int main()
{
    int x, y, s;
    char c;
    vector<vector<int>> v(14, vector<int>(14, 0));
    while (cin >> x >> c >> y >> c >> s) {
        x += 2; y += 2;
        switch (s) {
            case 3:
                v[x][y-2]++; v[x][y+2]++;
                v[x-2][y]++; v[x+2][y]++;
            case 2:
                v[x-1][y-1]++; v[x-1][y+1]++;
                v[x+1][y-1]++; v[x+1][y+1]++;
            case 1:
                v[x+1][y]++; v[x-1][y]++;
                v[x][y-1]++; v[x][y+1]++;
                v[x][y]++;
                break;
        }
    }

    int mx = 0, cnt = 0;
    for (int i = 2; i < 12; i++) {
        for (int j = 2; j < 12; j++) {
            mx = max(mx, v[i][j]);
            if (v[i][j] == 0) cnt++;
        }
    }
    cout << cnt << "\n" << mx << endl;
    return 0;
}

Measured memory_bytes: 3012
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main() {
    string s;
    cin >> s;
    int ans = 0;
    for(int i = 0; i < s.size() - 1; i++){
        if(s[i] != s[i + 1]){
            ans++;
        }
        }
        cout << ans << endl;

        return 0;
}

Measured memory_bytes: 512
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

double p, e, t;

double calc(int rest, double left, double right) {
  if (t - e <= left && right <= t + e) { return 1.0; }
  if (right < t - e || t + e < left) { return 0.0; }
  double mid = (left + right) / 2.0;
  if (rest == 0) {
    return t - e <= mid && mid <= t + e ? 1.0 : 0.0;
  }
  double ret = 0.0;
  if (mid <= t) {
    ret += (1.0 - p) * calc(rest - 1, mid, right);
    ret += p * calc(rest - 1, left, mid);
  } else {
    ret += (1.0 - p) * calc(rest - 1, left, mid);
    ret += p * calc(rest - 1, mid, right);
  }
  return ret;
}

int main() {
  int k;
  double l, r;
  while (scanf("%d %lf %lf", &k, &l, &r) > 0) {
    scanf("%lf %lf %lf", &p, &e, &t);
    double ans = calc(k, l, r);
    printf("%.12f\n", ans);
  }
}

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


typedef long long ll;

#define fast ios::sync_with_stdio(0),cin.tie(0)

const int MS = 2e6 + 5, mod = 1e9 + 7;

ll fact[MS];

// calculating factorial 
void cal_fact()
{
    fact[0] = 1;
    for (int i = 1; i < MS; i++)
    {
        fact[i] = i * fact[i - 1];
        fact[i] %= mod;
    }
}
// modular exponentiation 
ll binpow(ll val, ll deg, ll mod)
{
    if (!deg)
        return 1 % mod;
    if (deg & 1)
        return binpow(val, deg - 1, mod) * val % mod;
    ll res = binpow(val, deg >> 1, mod);
    return (res * res) % mod;
}

ll cal_c(ll n, ll i)
{
    ll res = fact[n]; 
    ll div = fact[n - i] * fact[i];
    div %= mod;
    // using fermat little theorum
    div = binpow(div, mod - 2, mod); // modular inverse  
    return (res * div) % mod; 
}

int main()
{
    cal_fact();
  	fast ;
    ll n, k;
    cin >> k;
    string s;
    cin >> s;
    n = s.size();

    ll ans = 0;
    for (int i = n; i <= n + k; i++)
    {
        ans+=cal_c(n+k,i)*binpow(25,n+k-i,mod);
        ans%=mod;
    }
    cout<<ans<<"\n";
}


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

int n;
int x[10],y[10];

double dist(int i,int j)
{
    double dx = x[i]-x[j];
    double dy = y[i]-y[j];
    
    return pow(dx*dx + dy*dy,0.5);
}

void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>x[i]>>y[i];
    
    double sum=0.0;
    vector<int> v(n);
    
    for(int i=0;i<n;i++)
    v[i]=i+1;
    
    do
    {
        for(int i=0;i<n-1;i++)
        sum+=dist(v[i],v[i+1]);
        
    }while(next_permutation(v.begin(),v.end()));
    
    int fac=1;
    
    for(int i=2;i<=n;i++)
    fac*=i;
    
    cout<<fixed<<setprecision(10)<<sum/fac<<endl;
    return;
}

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
using vll = vector<vl>;
using Pll = pair<ll, ll>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(v) v.begin(), v.end()
#define sz(x) ((int) x.size())
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
const int MOD = 1e9+7;
const ll INF = 2e15;
template<class T> void print(const T& t){ cout << t << endl; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

int main(){
  string s;
  cin>>s;
  if(s[sz(s)-1]=='s'){
    cout<<s<<"es"<<endl;
  }
  else{
    cout<<s<<"s"<<endl;
  }
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();
int main()
{
    string S;
    cin >> S;

    if( S[ 0 ] != 'A' || isupper( S[ 1 ] ) || isupper( S[ (int)S.size() - 1 ] ) )
    {
        cout << "WA" << endl;
        return 0;
    }
    bool flag = false;
    int cnt{};
    for( int i = 2; i < (int)S.size() - 1; ++i )
    {
        if( S[ i ] == 'C' )
        {
            flag = true;
            cnt++;
        }
        if( cnt >= 2 )
        {
            cout << "WA" << endl;
            return 0;
        }
    }
    for( int i = 2; i < (int)S.size() - 1; ++i )
    {
        if( S[ i ] == 'C' ) continue;
        if( isupper( S[ i ] ) )
        {
            flag = true;
        }
    }
    cout << ( flag ? "AC" : "WA" ) << endl;
    return 0;
}

Measured memory_bytes: 256
import java.io.*;

public class Main {
  public static void main(String[] args) {
    new Main().run();
  }

  private void run() {
    try(BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out)) {

        String[] lines = in.readLine().split(" ");
        int a = Integer.parseInt(lines[0]);
        int b = Integer.parseInt(lines[1]);

        int ans = 0;
        if(0 <= a && a < 6) ans = 0;
        else if(a <13) ans = b / 2;
        else ans = b;

        System.out.println(ans);
    }
    catch(IOException e) {
      System.err.println(e);
    }
  }
}

Measured memory_bytes: 20692
#include <algorithm>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

int main() {
  int N;
  vector<int64_t> var(3);
  cin >> N >> var[0] >> var[1] >> var[2];

  vector<int> op;
  rep(i, N) {
    string s;
    cin >> s;

    if (s == "AB") {
      op.push_back(0);
    } else if (s == "BC") {
      op.push_back(1);
    } else {
      op.push_back(2);
    }
  }

  int64_t S = var[0] + var[1] + var[2];
  vector<int> result;
  if (S == 0) {
    cout << "No\n";
    return 0;
  } else if (S == 1) {
    rep(i, N) {
      int j = op[i];
      if (var[j] == 0 && var[(j + 1) % 3] == 0) {
        cout << "No\n";
        return 0;
      } else {
        result.push_back((var[j] < var[(j + 1) % 3] ? j : (j + 1) % 3));
        swap(var[j], var[(j + 1) % 3]);
      }
    }
  } else {
    if (var[op[0]] == 0 && var[(op[0] + 1) % 3] == 0) {
      cout << "No\n";
      return 0;
    }
    rep(i, N) {
      int j = op[i];
      if (i == N - 1) {
        var[j]++;
        var[(j + 1) % 3]--;
        if (var[0] >= 0 && var[1] >= 0 && var[2] >= 0) {
          result.push_back(j);
        } else {
          var[j] -= 2;
          var[(j + 1) % 3] += 2;
          result.push_back((j + 1) % 3);
        }
      } else {
        int k = op[i + 1];
        var[j]++;
        var[(j + 1) % 3]--;
        if (var[0] >= 0 && var[1] >= 0 && var[2] >= 0 &&
            (var[k] > 0 || var[(k + 1) % 3] > 0)) {
          result.push_back(j);
        } else {
          result.push_back((j + 1) % 3);
          var[j] -= 2;
          var[(j + 1) % 3] += 2;
        }
      }
    }
  }

  cout << "Yes\n";
  rep(i, N) { cout << (char)("ABC"[result[i]]) << "\n"; }

  cerr << var[0] << " " << var[1] << " " << var[2] << "\n";
  return 0;
}

Measured memory_bytes: 4248
#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
char grid[12][12];
void dfs(int x,int y){
grid[x][y]='0';
for(int dx=-1;dx<=1;dx++){
	for(int dy=-1;dy<=1;dy++){
       if(dx!=0&&dy!=0){continue;}
		if(dx==dy&&dy==0){continue;}
      int nx=x+dx,ny=y+dy; 
		if(0<=nx&&nx<12&&0<=ny&&ny<12){
		if(grid[nx][ny]=='1'){dfs(nx,ny);}
		}
	}
	
}		
return ;
}
int main(){
  
while(cin>>grid[0][0])
{
for(int i=0;i<12;i++)
{
for(int j=0;j<12;j++){
if(i==0&&j==0){continue;}
cin>>grid[j][i];
}
}
int ret=0;
for(int j=0;j<12;j++){
	for(int i=0;i<12;i++){
	  	if(grid[j][i]=='1'){
			dfs(j,i);
			ret++;
		}
	}
}
cout<<ret<<endl;

}
return 0;
}


Measured memory_bytes: 3016
import java.util.*;

public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        //final int n = sc.nextInt();
        final double w = sc.nextDouble();
        final double h = sc.nextDouble();
        final double x = sc.nextDouble();
        final double y = sc.nextDouble();

        final double ansArea = (w*h)/2;
        int ansPattern = 0;
        if (x*2 == w && y*2 == h) ansPattern = 1;
        System.out.println(ansArea+" "+ansPattern);

        sc.close();
    }
}

Measured memory_bytes: 23380
import sys

# utils
def read_numbers():
    return [int(num) for num in sys.stdin.readline().split()]
def read_string():
    return sys.stdin.readline().rstrip('\r\n')
def list2str(*array):
    return ' '.join([str(i) for i in array])

def main(N, A):
    return N*N - A

def parse_stdin():
    # N = read_numbers()
    # data = []
    # for i in range(N):
    #    data.append(read_numbers())
    N = read_numbers()[0]
    A = read_numbers()[0]
    return N, A

def test_main():
    """run pytest stdin.py to test"""
    #assert main([1,2], 'hi') == '3 hi'
    pass

if __name__ == '__main__':
    N, A = parse_stdin()
    result = main(N, A)
    print(result)

Measured memory_bytes: 3188
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <iomanip>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

#define debug(x) cout << #x << " = " << x << endl
#define fori(i, ini, lim) for(int i = int(ini); i < int(lim); i++)
#define ford(i, ini, lim) for(int i = int(ini); i >= int(lim); i--)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;

const int MAX = 2e5 + 5;
map<int, int> atcoder[MAX];
vector<int> adj[MAX];
ll ans[MAX];
int color[MAX];
int n;

int dfs(int source, int father) {
    int size = 1;
    int c = color[source];
    for (auto &each : adj[source]) {
        if (each == father) continue;
        int each_size = dfs(each, source);
        size += each_size;
        int not_my_color = each_size - atcoder[each][c];
        ans[c] += (1LL * not_my_color * (not_my_color + 1)) / 2;
        if (atcoder[each].size() > atcoder[source].size()) swap(atcoder[source], atcoder[each]);
        for (auto &d : atcoder[each]) {
            atcoder[source][d.first] += d.second;    
        }
    }
    int not_my_color = (size - 1) - atcoder[source][c];
    atcoder[source][c] += not_my_color + 1;
    return size;
}

void solve() {
    cin >> n;
    fori (i, 1, n + 1) cin >> color[i];
    fori (i, 0, n - 1) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, -1);
    fori (i, 1, n + 1) {
        int c = i;
        if (c == color[1]) continue;
        int not_my_color = n - atcoder[1][c];
        ans[c] += (1LL * not_my_color * (not_my_color + 1)) / 2;
    }
    ll total_paths = (1LL * n * (n + 1)) / 2;
    fori (i, 1, n + 1) cout << total_paths - ans[i] << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}



Measured memory_bytes: 72264
//nani?
#include<bits/stdc++.h>
#define pi acos(-1);
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define f(i,a,b) for( int i = a; i < b ; i++ )
#define sor(a) sort( a.begin(), a.end() )
#define rsor(a) sort( a.rbegin(), a.rend() )
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
//#define inf 1LL<<62
typedef long long ll;
typedef double ld;
using namespace std;
const ll inf=1e10+6;
const ll MOD=1e9+7;
const ll mod=998244353;
// ac cmtr;
const int MAX_N = 2e5+5;
const int LG = 25;

#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cout << name << " : " << arg1 << endl;}
 
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cout.write(names, comma - names) << " : " << arg1<<" | ";
  __f(comma+1, args...);}
#else
#define trace(...)
#endif
//---------------------------

//pair <ll,ll> a[MAX_N];

int main(){
    fastio;
  	//cout<<fixed<<setprecision(0);
  	long double n,m;
  	cin>>n>>m;
  	long double ans = n*m;
  	unsigned long long ans1 = ans + .001;
  	cout<<ans1<<endl;
}

Measured memory_bytes: 3736
n,a,b = map(int, input().split())

MOD = 10**9 + 7
fact_inv, inv = [0]*10**6, [0]*10**6

def init_nCk():
    fact_inv[0] = fact_inv[1] = 1
    inv[1] = 1
    for i in range(2,10**6):
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        fact_inv[i] = fact_inv[i-1] * inv[i] % MOD

def nCk(n,k):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    ans = 1
    for i in range(n, n-k+1 - 1, -1):
        ans *= i
        ans %= MOD
    return ans * fact_inv[k] % MOD


init_nCk()
ans = (pow(2,n,MOD)-nCk(n,a)-nCk(n,b) - 1)%MOD
print(ans)

Measured memory_bytes: 82164
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,(n)-1,0)
#define all(v) v.begin(), v.end()
#define endk '\n'
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;
const ll mod2 = 998244353;
const ld eps = 1e-10;
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b){if(a>b) a=b;}
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b){if(a<b) a=b;}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n; cin >> n;
  vector<ll> A(n); rep(i, n) cin >> A[i];
  sort(all(A));
  cout << *A.rbegin() - *A.begin() << endk;
  return 0;
}


Measured memory_bytes: 3636
#include <iostream>
#include <tuple>
#include <sstream>
#include <vector>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cassert>
#include <cstdio>
#include <queue>
#include <set>
#include <map>
#include <fstream>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

i64 cnt[26];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;
#ifdef LOCAL_DEFINE
    freopen("input.txt", "rt", stdin);
#endif

    string s;
    cin >> s;
    i64 ans = 1;
    for (char c: s) ++cnt[c - 'a'];
    forn(i, 26) forn(j, i) ans += cnt[i] * cnt[j];
    cout << ans << '\n';

#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}


Measured memory_bytes: 720
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i ,n) for(int i = 0 ; i < (n) ; i ++ )
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
using ll = long long;
using vin=vector<int>;
using vll=vector<ll>;
using P = pair<int, int>;
const int inf=1e9+7;
const ll INF=1e18;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

int main() {
int n;
  ll ans=0;
  cin>>n;
  vin v(n);
  rep(i,n) cin>>v[i];
  map<int,int> mp1,mp2;
  for(int i=0;i<n;i+=2){
   mp1[v[i]]++; 
  }
  for(int j=1;j<n;j+=2){
   mp2[v[j]]++; 
  }
  int cnt1=0,cnt2=0;
  int key1=0,key2=0;
  int ar1=0,ar2=0;
  for(auto v:mp1){
    if(v.second>=cnt1){
     
     cnt1=v.second;
      key1=v.first;
    }
  }
  for(auto v:mp2){
    if(v.second>=cnt2){
      
     cnt2=v.second;
      key2=v.first;
    }
  }
  if(key1!=key2){
    
     ans=n-cnt1-cnt2;
  }
  else{//key1==key2
    mp1[key1]=0;
    mp2[key1]=0;
    for(auto v:mp1){
    if(v.second>=ar1){
     
     ar1=v.second;
      
    }
  }
  for(auto v:mp2){
    if(v.second>=ar2){
      
     ar2=v.second;
      
    }
  }
    ans=n-max(ar1+cnt2,ar2+cnt1);
  }
    
    
    //cout<<ar1<<" "<<ar2<<" "<<cnt1<<" "<<cnt2<<endl;
    cout<<ans<<endl;
}




Measured memory_bytes: 5376
import java.util.Scanner;

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

		char[] s = sc.nextLine().toCharArray();
		int n = s.length;

		int[][] dp = new int[n + 1][2];
		dp[0][0] = 1;

		for (int i = 0; i < n; i++) {
			// ---- a & b == 0
			if (s[i] == '0') {
				dp[i + 1][0] = dp[i][0];
				dp[i + 1][1] = dp[i][1];
			} else {
				dp[i + 1][1] = (dp[i][0] + dp[i][1]) % M;
			}

			// ---- a & b == 1
			if (s[i] == '0') {
				dp[i + 1][1] += (dp[i][1] * 2) % M;
				dp[i + 1][1] %= M;

			} else {
				dp[i + 1][0] += (dp[i][0] * 2) % M;
				dp[i + 1][1] += (dp[i][1] * 2) % M;
				dp[i + 1][0] %= M;
				dp[i + 1][1] %= M;
			}
		}

		System.out.println((dp[n][0] + dp[n][1]) % M);
	}
}


Measured memory_bytes: 27724
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll dp[401][401];
ll sum[401][401];
ll a[401];
ll solve(ll n)
{
	for(ll p=1;p<=n;p++)
	{
		dp[p][p]=0;
	}
	for(ll i=1;i<=n;i++)
	{
		sum[i][i]=a[i];
		for(ll j=i+1;j<=n;j++)
		{
			sum[i][j]=sum[i][j-1]+a[j];
		}
	}
	for(ll length=2;length<=n;length++)
	{
		for(ll i=1;i<=n-length+1;i++)
		{
			ll j=i+length -1;
			dp[i][j]=1e14;
			for(ll k=i;k<=j;k++)
			{
				dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[i][j]);
			}
		}
	}
	return dp[1][n];
}
int main()
{
	ll n;
	cin>>n;
	for(ll p=1;p<=n;p++)
	{
		cin>>a[p];
	}
	cout<<solve(n);
}

Measured memory_bytes: 6052
#include<stdio.h>
#include<bitset>
template<class T>
T LCM(T x, T y)
{
	T z;
	while( (z=x%y) != 0)
	{
		x = y;
		y = z;
	}
	return y;
}
template<class T>
T GCD(T x,T y)
{
	return x/LCM(x,y)*y;
}
int main()
{
	int a1,a2,a3,m1,m2,m3,i,j;

	while(scanf("%d%d%d%d%d%d",&a1,&m1,&a2,&m2,&a3,&m3), a1)
	{
		int c1,c2,c3;
		int v1,v2,v3;
		for(v1 = a1, c1 = 1; v1 != 1; ++c1)
			v1 = (v1*a1 % m1);
		for(v2 = a2, c2 = 1; v2 != 1; ++c2)
			v2 = (v2*a2 % m2);
		for(v3 = a3, c3 = 1; v3 != 1; ++c3)
			v3 = (v3*a3 % m3);
		printf("%Ld\n", GCD((long long)c1, GCD((long long)c2,(long long)c3)) );
	}
	return 0;
}

Measured memory_bytes: 0
h, w = map(int, input().split())
alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
for i in range(1, h + 1):
    row = list(input().split())
    for j in range(w):
        if row[j] == "snuke":
            print(alpha[j] + str(i))
            exit()

Measured memory_bytes: 3060
#include <stdio.h>
 
#define DEBUG	(0)

int main(void)
{
  int array[32] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  int k = 0;
  
  scanf("%d",&k);
  
  printf("%d\n",array[k-1]);
  
  
}

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

int gcd(int x, int y){
  int r;
  while((r= x % y)!=0){x=y; y=r;}
  return y;
}

int main(){
  int N,X;
  cin >> N >> X;
  vector<int> x(N);
  for(int i=0;i<N;i++)cin >> x[i];
  sort(x.begin(),x.end());
  int d=abs(X-x[0]);
  for(int i=0;i<N-1;i++){d=gcd(d,x[i+1]-x[i]);}
  cout << d << endl;
}

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

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using pint = pair<int, int>;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const int MOD = 1000000009;
const long long INF = 1LL << 60;

int main() {
    string S;
    int Q;
    cin >> S >> Q;
    deque<char> dq(S.size());
    for (int i = 0; i < S.size(); ++i) dq[i] = S[i];
    bool flip = false;
    for (int i = 0; i < Q; ++i) {
        int T;
        cin >> T;
        if (T == 1) flip = !flip;
        else {
            int F;
            cin >> F;
            if (F == 1) {
                char C;
                cin >> C;
                if (flip) dq.push_back(C);
                else dq.push_front(C);
            }
            if (F == 2) {
                char C;
                cin >> C;
                if (flip) dq.push_front(C);
                else dq.push_back(C);
            }
        }
    }
    if (flip) reverse(dq.begin(), dq.end());
    for (auto&& ele : dq) cout << ele;
    cout << endl;
    
    return 0;
}

Measured memory_bytes: 4036
#include <algorithm>
#include <iostream>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <iterator>
#include <map>
#include <set>
#include <iomanip>
#include <vector>
#include <cstdint>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Graph = vector<vector<int>>;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
#define rep(i, N) for(int i = 0; i < N; i++)
#define rep2(i, l, r) for (ll i = (ll)l; i < (ll)(r); i++)
#define INF 1000000000
#define MAX 200001
#define PI 3.141592653589793

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
const ll MOD = 1000000007;

template <typename T > inline string toString(const T &a) {ostringstream oss; oss << a; return oss.str();};

set<string> s;
int ans = 0;

void dfs(int idx,string now, int N, string S){
    if(now.size() == 3){
        ans++;
        return;
    }
    for(int i = idx; i < N; i++){
        string new_s = now + S[i];
        if(s.find(new_s) != s.end()) continue;
        s.insert(new_s);
        dfs(i+1,new_s,N,S);
    }
}

int main(){
    int N;
    cin >> N;
    string S;
    cin >> S;
    dfs(0,"",N,S);
    cout << ans << endl;
}

Measured memory_bytes: 3812
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
typedef vector<vector<P>> vvP;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;
 
const ll dx[4] = {1, 0, -1, 0};
const ll dy[4] = {0, 1, 0, -1};
 
int main() {
    ll h, w;
    cin >> h >> w;
    
    vector<string> board(h);
    rep(i, h) {
        cin >> board[i];
    }
    
    ll ans = 0;
    rep(sx, h) {
        rep(sy, w) {

            if(board[sx][sy] == '#') {
                continue;
            }

            vvl matrix(h, vl(w, -1));  // 数字を書き込むマス。-1で初期化
            queue<pair<ll, ll>> next;  // 次に探索するマスを入れるqueue
            
            next.push(make_pair(sx, sy));
            matrix[sx][sy] = 0;
            while(!next.empty()) {  // nextが空になるまで探索
                ll x = next.front().first;
                ll y = next.front().second;
                // 4方向調べる
                rep(i, 4) {
                    ll nx = x + dx[i];
                    ll ny = y + dy[i];
                    // 盤外または探索済みのところはダメ
                    if(nx < 0 || h <= nx || ny < 0 || w <= ny || 0 <= matrix[nx][ny]) {   
                        continue;
                    }
                    if(board[nx][ny] == '#') {
                        continue;
                    }
                    matrix[nx][ny] = matrix[x][y] + 1;  // 隣接マスに1足す
                    next.push(make_pair(nx, ny));  // 隣接マスをnextに入れる
                }
                next.pop();  // nextからいま探索したマスを削除
            }
 
            ll now = 0;
            rep(i, h) {
                rep(j, w) {
                    chmax(now, matrix[i][j]);
                }
            }
 
            chmax(ans, now);
        }
    }
 
    out(ans);
    re0;
}

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

int main(){
    int k; cin >> k;
    string s; cin >> s;
    if(k >= s.size()) cout << s << endl;
    else{
        for(int i = 0; i < k; i++) cout << s[i];
        cout << "..." << endl;
    }
}

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

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


int main() {
long long  n,T;cin>>n>>T;
long long t[n];rep(i,n)cin >> t[i];
long long count =0;


for(int i=0;i<n;i++){ 
    if(i!=n-1)count += min(T,t[i+1]-t[i]);
    else count +=T;
}
cout << count<< endl;
return 0;           

}


Measured memory_bytes: 1792
#include <cstdio>
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <tuple>
#include <assert.h>
#include <deque>
#include <bitset>
#include <iomanip>
#include <limits>
#include <chrono>
#include <random>
#include <array>
#include <unordered_map>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const long long MAX = 5100000;
const long long INF = 1LL << 60;
const long long MOD = 1'000'000'007LL;
const long long mod = 998244353LL;

using namespace std;
typedef unsigned long long ull;
typedef long long ll;

ll power(ll x, ll n, ll p = 1000000007) {
	if (n == 0) {
		return 1;
	}
	if (n % 2 == 0) {
		return power(x * x % p, n / 2, p) % p;
	}
	else {
		return x * power(x, n - 1, p) % p;
	}
}

int main()
{
	/*
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	*/
	ll n, k; cin >> n >> k;

	cout << power(k, n) << endl;
	return 0;
}


Measured memory_bytes: 3116
s, T = input()[::-1], input()[::-1]
#後ろから見る

def is_T(s_i, T_i):
    if len(T_i) == 1:
        if s_i[0] == T_i[0] or s_i[0] == '?':
            return True
    
    if s_i[0] == T_i[0] or s_i[0] == '?':
        flag = is_T(s_i[1:], T_i[1:])
        
        if flag:
            return True
    
    return False

for i in range(len(s)-len(T)+1):
    result = is_T(s[i:], T)
    if result:
        ans = ''
        for j in range(i):
            if s[j] != '?':
                ans += s[j]
            else:
                ans += 'a'
        ans += T
        for j in range(len(ans), len(s)):
            if s[j] != '?':
                ans += s[j]
            else:
                ans += 'a'
        print(ans[::-1])
        break
else:
    print('UNRESTORABLE')

Measured memory_bytes: 3064
#include <iostream>
#include <limits.h>
using namespace std;
int main(void) {

	int n;
	int max = INT_MIN, min = INT_MAX;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int temp;
		cin >> temp;
		max = ((max > (temp - min)) ? max : temp - min);
		min = ((min < temp) ? min : temp);
	}
	cout << max << endl;
	return 0;
}


Measured memory_bytes: 3112
integer,allocatable,dimension(:)::DP
integer N,M
integer a,mo
read*,N,M
allocate(DP(0:N))
mo=1000000007
DP=-1
do i=1,M
  read*,a
  DP(a)=0
end do
DP(0)=1
if(DP(1)==-1)DP(1)=1
do i=2,N
  if(DP(i)==-1)DP(i)=mod(DP(i-1)+DP(i-2),mo)
end do
print"(I0)",DP(N)
end

Measured memory_bytes: 640
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int q  = sc.nextInt();
        long a, b;
        for(int i=0; i<q; i++){
            long tmpa = sc.nextLong();
            long tmpb = sc.nextLong();
            if(tmpa > tmpb){
                a = tmpb;
                b = tmpa;
            }else{
                a = tmpa;
                b = tmpb;
            }
            long ans = 0;
            ans += (a-1) * 2;

            int count = 0;
            long score = a*b;
            
            int l = 1;
            int r = 1000000000;
            while(r > l+1){
                int m = (l+r) / 2;
                if((long)m * (long)m < score){
                    l = m;
                }else{
                    r = m-1;
                }
            }
            if(l!= r && (long)(l+1) * (long)(l+1) < score) l++;

            if(l > a && l < b) ans += (l - a) * 2;
            if((long)l * (long)(l + 1) < score && l+1 != b) ans++;
            System.out.println(ans);
        }

    }
}

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

typedef long long ll;
 
using tpl = tuple<int, int, int>;
typedef pair<int,int> pii;

void fastStream(){cin.tie(0);std::ios_base::sync_with_stdio(0);}

const int mod = 1000000000 + 7;

int N;
vector<int> G[100010];
ll dp[100010][3];

ll dfs(int pos, int par, int par_col){
    if(dp[pos][par_col] >= 0) return dp[pos][par_col];
    ll res = 0;
    for(int col = 0; col < 2; col++){
        if(par_col == 1 && col == 1) continue;
        ll tmp = 1;
        for(int to : G[pos]){
            if(to == par) continue;
            (tmp *= dfs(to, pos, col)) %= mod;
        }
        (res += tmp) %= mod;
    }
    return dp[pos][par_col] = res;
}

int main() {
    cin >> N;
    for(int i = 0; i < N - 1; i++){
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    memset(dp, -1, sizeof(dp));
    cout << dfs(0, N + 1, 2) << endl;
    

    return 0;
}


Measured memory_bytes: 17792
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
const int MAX_N= 2e5+5, MAX_M = 2e5+10;
int n, m;
int a[MAX_M],b[MAX_M];
int par[MAX_N];
 
void init()
{
	for(int i=1;i<=n;++i) par[i]=i;
}
 
int look(int x)
{
	if(x == par[x]) return x;
	else return par[x]=look(par[x]);
}
 
void comb(int x, int y)
{
	int p=look(x),q=look(y);
	if(p!=q){
		par[q] = p;
	}
}
 
void solve()
{
    init();
	int comp = n;
	for(int i=0;i<m;++i){
		if(look(a[i])!=look(b[i])){
			comp--;
		}
		comb(a[i],b[i]);
	}
	if(comp == 1){
		cout<<0<<'\n';
	}else{
		cout<<comp-1<<'\n';
	}
}
 
int main()
{
	cin >> n >> m;
	for(int i=0;i<m;++i){
		cin >> a[i] >> b[i];
	}
	solve();
	return 0;
}

Measured memory_bytes: 4784
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <iomanip>
#include <map>
#include <set>
#include <cmath>
#include <cstdio>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define FOR(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define All(v) (v).begin(),(v).end()
typedef long long ll;
using pll = pair<ll,ll>;

int main(){
    ll N,W;
    cin >> N >> W;
    vector<vector<ll> > object(4);
    ll w0 = 0;
    rep(i,N){
        int a,b;
        cin >> a >> b;
        if(i==0)w0=a;
        object[a-w0].push_back(b);
    }
    rep(i,4){
        sort(All(object[i]));
        reverse(All(object[i]));
    }
    vector<vector<ll> > sum(4);
    rep(i,4){
        int s = object[i].size()+1;
        sum[i].resize(s);
        rep(j,s-1){
            sum[i][j+1]=sum[i][j]+object[i][j];
        }
    }
    ll res = 0;
    for(int i=0;i<sum[0].size();i++){
        for(int j=0;j<sum[1].size();j++){
            for(int k=0;k<sum[2].size();k++){
                for(int l=0;l<sum[3].size();l++){
                    ll v = sum[0][i]+sum[1][j]+sum[2][k]+sum[3][l];
                    ll w = w0*i+(w0+1)*j+(w0+2)*k+(w0+3)*l;
                    if(w<=W)res = max(res,v);
                }
            }
        }
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, m;
  cin >> n;
  cin >> m;
  vector<vector<char>> z(n+1, vector<char>(m+1));
  vector<string> h(n+1);
    for (int i = 1; i < n+1; i++) {
      cin >> h.at(i);
        for(int j = 1; j < m+1;j++){
          z.at(i).at(j) = h.at(i).at(j-1);
        }
  }
  vector<vector<int>> x(n+1, vector<int>(m+1));
  int count = 0;
  x.at(0).at(1) = 2;
  for(int k = 2; k < 210; k++) {
    char p;
    if (k % 2 == 0){
      p = '.';}
    else{
    p = '#';}
   for (int i = 1; i < n+1; i++) {
    for (int j = 1; j < m+1; j++) {
      if((x.at(i-1).at(j) == k-1 || x.at(i).at(j-1) == k-1 || x.at(i-1).at(j) == k || x.at(i).at(j-1) == k) && z.at(i).at(j) == p)
         {x.at(i).at(j) = k;
         }
      
         }
         }
         if(x.at(n).at(m) > 0){break;}
         }
    count = (x.at(n).at(m) - 1) / 2;
         cout << count << endl;
         }

Measured memory_bytes: 384
list = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
S = input()
S = int(S)
print(list[S-1])

Measured memory_bytes: 3060
def resolve():
    a = list(map(int, input().split()))
    a += list(map(int, input().split()))
    a += list(map(int, input().split()))
    n = int(input())
    b = [0]*n
    for i in range(n):
        b[i] = int(input())
    c = [False] * 9
    ans = False
    for i in range(9):
        c[i] = a[i] in b
    if c[0] and c[1] and c[2]:
        ans = True
    if c[3] and c[4] and c[5]:
        ans = True
    if c[6] and c[7] and c[8]:
        ans = True
    if c[0] and c[3] and c[6]:
        ans = True
    if c[1] and c[4] and c[7]:
        ans = True
    if c[2] and c[5] and c[8]:
        ans = True
    if c[0] and c[4] and c[8]:
        ans = True
    if c[2] and c[4] and c[6]:
        ans = True
    print("Yes" if ans else "No")


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 3064
#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n = int(input())
    s = input()
    min_ = float('inf')
    lw = 0
    le = 0
    rw = s.count('W')
    re = s.count('E')

    # 1番目 [0]番目はあらかじめ計算する
    if s[0] == 'W':
        rw -=1
    else:
        re -=1
    min_ = min(min_,lw+re)
    for i in range(1,n):
        if s[i] == 'W':
            rw -=1
        else:
            re -=1
        if s[i-1] == 'W':
            lw += 1
        else:
            le += 1
        min_ = min(min_,lw + re)
    print(min_)

if __name__ == '__main__':
  main()


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

int main()
{
    int a,b;
    char c;
    cin>>a>>b;
    string s1="",s2="";
    for(int i=0; i<a; i++)
    {
        c=b+'0';
        s1+=c;
    }
    for(int i=0; i<b; i++)
    {
        c=a+'0';
        s2+=c;

    }
    if(s1.size()>s2.size())
    {
        for(int i=0; i<s1.size(); i++)
        {
            if((s1[i]-'0')<(s2[i]-'0'))
            {
                cout<<s1;
                return 0;
            }
            else if((s1[i]-'0')>(s2[i]-'0'))
            {
                cout<<s2;
                return 0;
            }
        }
    }
    else
    {
        for(int i=0; i<s2.size(); i++)
        {
            if((s1[i]-'0')<(s2[i]-'0'))
            {
                cout<<s1;
                return 0;
            }
            else if((s1[i]-'0')>(s2[i]-'0'))
            {
                cout<<s2;
                return 0;
            }
        }
    }
    cout<<s1;
    return 0;
}


Measured memory_bytes: 3596
#define _USE_MATH_DEFINES
#include <array>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>

using namespace std;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 29;
const int MOD = 1e9 + 7;

const int N = 5e3 + 10;
char s[N];
int lcp[N][N];

int main() {
  int n;
  scanf("%d%s", &n, s);
  int ret = 0;
  for (int i = n - 1; i >= 0; --i) {
    for (int j = n - 1; j >= i; --j) {
      lcp[i][j] = s[i] == s[j] ? 1 + lcp[i + 1][j + 1] : 0;
      int len = min(j - i, lcp[i][j]);
      ret = max(ret, len);
    }
  }
  printf("%d\n", ret);
  return 0;
}


Measured memory_bytes: 96896
def main():
    t = int(input())
    arr = list(input())

    count = 0
    left = 0
    right = t-1

    # W R W W R W R R

    while left < right:
        if arr[right] == 'R' and arr[left] == 'W':
            # arr[left], arr[right] = arr[right], arr[left]
            left += 1
            right -= 1
            count += 1

        elif arr[left] == 'R' and arr[right] =='R' :
            left += 1

        elif arr[left] == 'W' and arr[right] =='W':
            # left += 1
            right -= 1
            # count += 1

        else:
            left += 1
            right -= 1




    print(count)




main()


Measured memory_bytes: 73332
(function (input) {
    var inputs = input.replace(/\r/g, '').split("\n"), tmp, i, j, len, n, k, progression, sum, sums, max;
    while(true) {
        progression = [];
        sums = [];
        tmp = inputs.shift().split(' ');
        n = parseInt(tmp[0]);
        k = parseInt(tmp[1]);
        if(n == 0 && k == 0) {
            break;
        }
        for(i = 0; i < n; i++) {
            tmp = parseInt(inputs.shift());
            progression.push(tmp);
        }
        max = progression[0] + progression[1] + progression[2];
        for(i = 0; i <= n - k; i++) {
            sum = 0;
            for(j = i; j < i + k; j++) {
                sum += progression[j];
            }
            if(sum > max) {
                max = sum;
            }
        }
        console.log(max);
    }
})(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 20444
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

using lint = long long;
using ldouble = long double;

const int INF = 1 << 30;

int main() {
    int N, D, X;
    cin >> N >> D >> X;
    vector<vector<int>> P(D, vector<int>(N));
    for (auto& v : P) {
        for (auto& p : v) cin >> p;
    }

    for (int d = 0; d < D - 1; ++d) {
        vector<int> dp(100010, -INF);
        dp[X] = 0;
        // dp[p] = p円残っているときの最大利益
        for (int i = 0; i < N; ++i) {
            if (P[d + 1][i] < P[d][i]) continue;
            for (int p = 100000 - P[d][i]; p >= 0; --p) {
                dp[p] = max(dp[p], dp[p + P[d][i]] + P[d + 1][i]);
            }
        }

        X = 0;
        for (int p = 0; p <= 100000; ++p) {
            X = max(X, p + dp[p]);
        }
    }

    cout << X << endl;
    return 0;
}



Measured memory_bytes: 3536
#include<bits/stdc++.h>
using namespace std;
int gcd(int x,int y,int z)
{
	int b;
	b=__gcd(x,y);
	return (__gcd(b,z));
}
int main()
{
	int n,j,i,k,sum=0;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			for(k=1;k<=n;k++)
			{
				sum=sum+gcd(i,j,k);
			}
		}
	}
	cout<<sum;
	return 0;
}

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

int main()
{
    int p;
    int s;
    char ch;
    std::set<int> st;
    int q;
    vector<int> vec;
    while(1)
    {
        cin >> p >> ch >> s;
        if(p == 0 && s == 0)
        {
            break;
        }
        vec.push_back(s);
    }
    for(int i=0; i<vec.size(); i++)
    {
        st.insert(vec[i]);
    }

    while(cin >> q)
    {
        auto itr = st.find(vec[q - 1]);
        cout << std::distance(itr, st.end()) << endl;
    }
    return 0;
}



Measured memory_bytes: 3028
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, k;
	cin >> n >> k;
	k--;
	cout << (n + k - 2) / k << endl;
	return 0;
}

Measured memory_bytes: 256
N = int(input())
T = [int(n) for n in input().split()]
M = int(input())

def main():
    t = sum(T)
    for _ in range(M):
        p, x = [int(s) for s in input().split()]
        print(t - T[p - 1] + x)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include <stdio.h>
int main(void){
    
    int H;
    int W;
    int N;
    
    int h;
    int w;
    
    int num;
    num = 0;
    
    int count;
    count = 0;
    
    scanf("%d",&H);
    h=H;
    scanf("%d",&W);
    w=W;
    scanf("%d",&N);
    
    while(num<N){
        if(H>=W && w>0) {
            num+=H;
            w--;
        }
        else if(h>0) {
            num+=W;
            h--;
        }

        count++;
    }
    printf("%d",count);
    
}


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

long long solve(vector<int>&a)
{
    int n=a.size();
    long long d=0;
    for(int i=0;i<n;i++){
            if(a[i]==0)continue;
        if(!(a[i]%2))
        {
            d+=a[i]/2;
        }
       else
        {
          d+=a[i]/2;
          if(i+1<n&&a[i+1]!=0){
            d++;
            a[i+1]--;
          }
        }
    }
    return d;
}
int main()
{
    int n;
    cin>>n;
    int i=0;
    vector<int>a(n);
    while(n--)
    {
    cin>>a[i++];
    }
    long long d=solve(a);
    cout<<d;
    return 0;
}


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

#define N 200000
#define DECIMAL 10

int main() {
    int k;
    cin >> k;

    vector<long> lunlunNumber;
    for (int i = 1; i <= 9; i++){
        lunlunNumber.push_back(i);
    }
    int first = 0;
    int last = 8;
    while (last < k){
        for (int i = first; i <= last; i++){
            long num = lunlunNumber.at(i);
            int leastPlaceNum = num % DECIMAL;
            if (leastPlaceNum != 0){
                lunlunNumber.push_back( num * DECIMAL + leastPlaceNum-1 );
            }
            lunlunNumber.push_back( num * DECIMAL + leastPlaceNum );
            if (leastPlaceNum != 9){
                lunlunNumber.push_back( num * DECIMAL + leastPlaceNum+1 );
            }
        }
        first = last + 1;
        last = lunlunNumber.size() - first - 1; 
    }
    
    cout << lunlunNumber.at(k-1) << endl;

    return 0;
}


Measured memory_bytes: 5344
#include<stdio.h>
#include<string.h>
#define LEN 100005

typedef struct pp{
  char name[100];
  int t;
}P;

P Q[LEN+1];
int head, tail, n;

void enqueue(P x){
  Q[tail] = x;
  if(tail == LEN){
    tail = 0;
  }else{
    tail++;
  } 
}

P dequeue(){
  P a;
  a = Q[head];
  if(head == LEN){
    head = 0;
  }else{
    head++;
  }  
  return a;
}


int main(){
  int elaps = 0;
  int i, q;
  P u;
  scanf("%d %d", &n, &q);

  for ( i = 1; i <= n; i++){
    scanf("%s", Q[i].name);
    scanf("%d", &Q[i].t);
  }
  
  head = 1;
  tail = n+1;
  
  while(head != tail){
    if(Q[head].t > q){
      Q[head].t -= q;
      elaps += q;
      enqueue(dequeue());
    }else{
      elaps += Q[head].t;
      printf("%s %d\n",Q[head].name,elaps);
      dequeue();
    }  
      
  }
  return 0;
}

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

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  int n; cin >> n;
  vector<int> p(n), q(n);
  for (int i = 0; i < n; ++i){
    cin >> p[i]; --p[i];
    q[p[i]] = i;
  }
  int now = 1, res = 0;
  for (int i = 1; i < n; ++i){
    res = max(res, now);
    if (q[i] > q[i - 1]) ++now;
    else now = 1;
  }
  res = max(res, now);
  cout << n - res;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb(a) push_back(a)
#define pbp(a,b) push_back({a,b})
#define rep(p,a,b)    for(int p=a;p<b;p++)
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define INF 0x3f3f3f3f

ll nextPowerOf2(ll n)   
{ 
	n--; 
	n |= n >> 1ll; 
	n |= n >> 2ll; 
	n |= n >> 4ll; 
	n |= n >> 8ll; 
	n |= n >> 16ll; 
	n++; 
	return n; 
}


int main() {
	
	#ifndef ONLINE_JUDGE
	// for getting input from input.txt
	freopen("input.txt", "r", stdin);
	// for writing output to output.txt
	freopen("output.txt", "w", stdout);
	#endif

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	ll n,t,i,k,sum;
	//cin>>t;
	t=1;
	while(t--)
	{

		cin>>n>>k;
		vector<int> v(n);
		rep(p,0,n)cin>>v[p];

		sort(v.begin(),v.end());
		sum=0;
		i=0;
		while(k--)sum+=(v[i++]);

		cout<<sum<<"\n";
	}

	return 0;
}

Measured memory_bytes: 3648
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <complex>
#include <ctime>
#include <cstdlib>

using namespace std;

inline int to_int(string s) {int v; istringstream sin(s); sin >> v; return v;}
template<class T> inline string to_str(T x) {ostringstream sout; sout << x; return sout.str();}

typedef long long ll;

int main()
{
	int n;
	vector<int> T(128);
	
	while(cin >> n, n)
	{
		for(int i = 0; i < n+1; i++)
		{
			cin >> T[i];
		}
		int res;

		for(int i = 0; i < n+1; i++)
		{
			vector<int> S = T;
			S.erase(S.begin() + i);
			int wid = S[1] - S[0]; bool ok = true;
			for(int j = 1; j < n; j++)
			{
				if(wid != S[j] - S[j-1])
				{
					ok = false;
					break;
				}
			}

			if(ok)
			{
				res = T[i];
				break;
			}
		}

		cout << res << endl;
	}
}

Measured memory_bytes: 1220
#include<iostream>
#include<algorithm>
#include<iomanip>
using lint=int64_t;
using namespace std;

int main()
{
	int N;

	cin >> N;

	cout << fixed << setprecision(7);
	cout << (N/2+(int)N%2)/(double)N << endl;
	return 0;
}


Measured memory_bytes: 256