akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define pb push_back
#define ss second
#define ff first
#define INF 300000000000001
#define ll_max 9000000000000000001
#define mod 1000000007
#define PI 3.14159265358979323846L
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define db(args...) {string _ss = #args; replace(_ss.begin(), _ss.end(), ',' , ' '); stringstream ___s(_ss) ; debug(___s, args);}
using namespace std;
typedef vector<pair<ll,ll> > vll;
typedef vector<pair<int,int> > vii ;
typedef pair<ll,ll> pll;
const ll N = 200001;
const ll M = 1;
struct point {
    ll x, y;
    ll i;
};

void debug(stringstream &s){}
template <typename T, typename... Args>
void debug(stringstream &s, T a, Args... args)
{
    string word;
    s >> word;
    cout << word << " = " << a << endl;
    debug(s, args...);
}

ll fast_exp(ll x, ll n)
{
    if(n == 0) return 1;
    else if(n & 1)
        return fast_exp(x, n - 1) * x % mod;
    else
    {
        ll tmp = fast_exp(x, n >> 1);
        return tmp * tmp % mod;
    }
}

vector<int> p;
void soe(int n = 1000001)
{
    bool P[n];
    P[0] = P[1] = 1;
    for(int i = 2; i < n; i++)
    {
        if(!P[i])
        {
            p.pb(i);
            for(int j = i + i; j < n; j += i)
            P[j] = 1;
        }
    }
}

vector<int> tree[N];
bool v[N];
ll loopStart, length, d[N];
void dfs(ll x, ll y = 0)
{
    if(v[x])
    {
        loopStart = x;
        length = y - d[x];
        return;
    }
    d[x] = y;
    v[x] = 1;
    dfs(tree[x][0], y + 1);
}

int main()
{
    fast;
    int _ = 1;
    //cin >> _;
    while(_--)
    {
        ll n, m, x = 0, y = 0, ans = 1, k = 0;
        cin >> n >> k;
        ll a[n + 1];
        for(int i = 1; i <= n; i++)
        {
            cin >> x;
            tree[i].pb(x);
            a[i] = x;
        }
        dfs(1);
        if(k > d[loopStart] + length)
        {
            k = k - d[loopStart];
            k = k % length;
            k += d[loopStart];
        }
        while(k--)
        {
            ans = a[ans];
        }
        cout << ans << "\n";
    }
    return 0;
}


Measured memory_bytes: 17904
#include <stdio.h>

int main(){
    int W,H;
    int x,y,r;
    
    scanf("%d %d %d %d %d", &W,&H,&x,&y,&r);
    
    if ( x - r >= 0 && x + r <= W && y - r >= 0 && y + r <= H){
        printf("Yes\n");
    }else{
        printf("No\n");
    }
    
    return 0;
} 

Measured memory_bytes: 584
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPD(i,n) for(int i=(n)-1;i>=0;--i)
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define FORD(i,a,b) for(int i=(a);i>=(b);--i)
#define TLE() cerr<<"\nTime elapsed: "<<1000*clock()/CLOCKS_PER_SEC<<"ms.\n";
const ll MOD = 1E9+7;
const ll IINF = 1E18;
const int INF = 1e9;
const double EPS = 1E-9;
const double PI = atan(1.0) * 4.0;
template<class T> T getbit(T s, int i) {return s>>i&1;}
template<class T> void flipbit(T& s, int i) {s^=(1LL<<i);}
constexpr int cntbit(ll x) {return __builtin_popcountll(x);}
constexpr int lg2(ll x) {return __lg(x);} // return int(log2(x))
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 
ll fpow(ll a,ll p){ll res=1LL;while(p){if(p&1LL) res=res*a%MOD;a=a*a%MOD;p>>=1LL;} return res;}

const int N=1e5+5;
int n,k,deg[N];
vector<int> adj[N];
ll f[N];

ll nPk(int x,int y){
	ll res=f[x];
	res=res*fpow(f[x-y],MOD-2)%MOD;
	return res;
}

ll go(int u,int p=-1){
	ll res;
	if(u!=1) res=nPk(k-2,deg[u]-1);
	else res=nPk(k-1,deg[u]);
	for(int v:adj[u])
		if(v!=p) res=res*go(v,u)%MOD;
	return res;
}

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>k;
	REP(i,n-1){
		int u,v;
		cin>>u>>v;
		adj[u].pb(v);
		adj[v].pb(u);
		++deg[u];
		++deg[v];
	}	
	FOR(u,1,n)
		if(deg[u]+1>k){
			cout<<0<<'\n';
			return 0;
		}
	f[0]=1;
	FOR(i,1,N-1) f[i]=f[i-1]*i%MOD;
	ll res=k*go(1)%MOD;
	cout<<res<<'\n';
}



Measured memory_bytes: 14876
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int max_n=20;
const int inf=0x3f3f3f3f;
int n,a[max_n],b[max_n];
int dp[1<<18][max_n];
int get(int x,int y){
    return (x^y)&1?b[x]:a[x];
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",a+i);
    for(int i=0;i<n;i++)scanf("%d",b+i);
    for(int s=1;s<(1<<n);s++){
        if(s&(s-1)){
            int c=__builtin_popcount(s);
            for(int i=0;i<n;i++){
                if(s>>i&1){
                    dp[s][i]=inf;
                    int t=s^(1<<i);
                    int cost=0;
                    for(int j=i+1;j<n;j++)if(s>>j&1)cost++;
                    for(int j=0;j<n;j++){
                        if((t>>j&1)&&get(j,c-2)<=get(i,c-1)){
                            dp[s][i]=min(dp[s][i],dp[t][j]+cost);
                        }
                    }
                }
            }
        }
    }
    int ans=inf;
    for(int i=0;i<n;i++)ans=min(ans,dp[(1<<n)-1][i]);
    if(ans!=inf)printf("%d\n",ans);
    else printf("-1\n");
    return 0;
}

Measured memory_bytes: 20736
#include <iostream>
#include <vector>
#include <cmath>

int main() {
    long long int n, t, planned = 0;
    std::cin >> n;
    std::vector<int> a(n+2);
    a[0] = 0;
    a[n+1] = 0;
    for (long long int i = 1; i <= n; i++) {
        std::cin >> t;
        a[i] = t;
        planned += abs(a[i] - a[i-1]);
    }
    planned += abs(a[n]);

    for (long long int i = 1; i <= n; i++) {
        std::cout << planned - abs(a[i] - a[i-1]) - abs(a[i+1] - a[i]) + abs(a[i-1] - a[i+1]) << std::endl;
    }

    return 0;
}

Measured memory_bytes: 1664
# -*- coding: utf-8 -*-

def solve():
    N = int(input())
    L = list(map(int, input().split()))
    if sum(L) - 2*max(L) > 0:
        res =  'Yes'
    else:
        res = 'No'
    return str(res)
if __name__ == '__main__':
    print(solve())

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

	int dp[10010];
	int sum[10010] = {0};
	int inf = 1222333444;

int main() {
	
	
	int m, n;
	int i, j;
	priority_queue <int> p;
	int c[500], e[500];
	
	cin >> m >> n;
	
	for(i = 0; i < m; i++) {
		int temp;
		cin >> temp;
		p.push(temp);
	}
	
	for(i = 0; i < n; i++) {
		cin >> c[i] >> e[i];
	}
	
	for(i = 0; i < 10010; i++) {
		dp[i] = inf;
	}
	
	dp[0] = 0;
	
	for(i = 0; i < n; i++) {
		for(j = m; j >= 1; j--) {
			dp[j] = min(dp[j], dp[max(j-c[i], 0)]+e[i]);
		}
	}

	
	int ans = 0;
	
	for(i = 1; i <= m; i++) {
		sum[i] = sum[i-1] + p.top();
		p.pop();
		ans = max(ans, sum[i] - dp[i]);
	}
	
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 1404
#include <bits/stdc++.h>
#include <math.h>
#include <cmath>
using namespace std;
using ll = long long;
using ull = unsigned long long;


int main (){
  ll x,y; cin >> x >> y;
  
  ll s = abs(x) - abs(y);
  ll t = abs(y) - abs(x);

  if(x >= 0 && y > 0){
    if(x > y){cout << s + 2 << endl;}
    else{cout << t << endl;}
  }
  else if(x >= 0 && y <= 0){
    if(abs(x) >= abs(y)){cout << s + 1 << endl;}
    else{cout << t + 1 << endl;}
  }
  else if(x < 0 && y > 0){
    if(abs(x) >= abs(y)){cout << s + 1 << endl;}
    else{cout << t + 1 << endl;}
  }
  else if(x < 0 && y <=0){
    if(abs(x) >= abs(y)){cout << s << endl;}
    else{cout << t + 2 << endl;}
  }
}

Measured memory_bytes: 256
//还需复习复习 
#include <iostream>

using namespace std;

const int N = 100; //最多矩阵个数 

int main() {
	int n;
	cin >> n;
	//储存连续相乘矩阵的行列 ，由矩阵相乘的性质，(r1*c1)*(c1*c2) = r1 * c2,因此不必重复存储中间的列或行 
	int *p = new int[n+1];
	int m[N+1][N+1] = {0}; //m[i][j] 存储着矩阵Mi*Mi+1*Mi+2*...*Mj的最少乘法次数
	for (int i=1;i<=n;i++) {
		cin >> p[i-1] >> p[i];
	}
	for (int l = 2;l<=n;l++) { //规模从2开始增加，先计算两两矩阵之间的代价 ，再计算三三矩阵之间的代价，四四之间的代价...
	    for (int i = 1;i<=n-l+1;i++) {
	    	int j = i + l -1;
	    	m[i][j] = 1 << 21; //先随便赋值一个大数，便于比较
	    	
	    	//此处与传递关系矩阵闭包有异曲同工之妙 
			for (int k = i;k<=j-1;k++) {
				m[i][j] = min(m[i][j],m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j]);
			}
		} 
		
	}
	cout << m[1][n] << endl;
	delete[] p; 
	return 0;
}


Measured memory_bytes: 3148
D = input()
a, b = [int(D[:2]), int(D[2:])]
if (a > 12 or a==0) and b != 0 and b <= 12:
  print('YYMM')
elif a != 0 and a <= 12 and (b > 12 or b == 0):
  print('MMYY')
elif a != 0  and a <= 12 and b != 0 and b <= 12:
  print('AMBIGUOUS')
else:
  print('NA')

Measured memory_bytes: 3064
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <climits>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1<<29;
const double PI = acos(-1);
const double EPS = 1e-8;
typedef pair<ll,int> pli;

int a[4000];
ll sum[4001];
short dp[4001][4001];
short prev[4001][4001];
ll v[4001][4001];
pli tv[4001];

int main() {
  int n;
  cin >> n;
  REP(i,n) cin >> a[i];
  sum[0] = 0;
  REP(i,n) sum[i+1] = sum[i] + a[i];
  REP(i,n)REP(j,n)dp[i][j]=-10000,prev[i][j]=-1;
  REP(i,n) {
    REP(j,i+1) {
      tv[j] = pli(sum[i+1]-sum[j], j);
    }
    sort(tv,tv+i+1);
    REP(j,i+1) {
      v[i][j] = tv[j].first;
    }
    REP(j,i+1) {
      ll a = tv[j].first;
      int b = tv[j].second;
      if (b==0) {
        dp[i][j] = 1;
      } else {
        //if (v[b-1][0] < a) {
          int k = lower_bound(v[b-1], v[b-1]+b, a)-v[b-1]-1;
          //cout << i <<" " << j << " " << v[i][j].first << "," << b-1 << " " << k << endl;
          if (k>=0) {
            if (dp[i][j] < dp[b-1][k] + 1) {
              dp[i][j] = dp[b-1][k] + 1;
              prev[i][j] = b-1;
            }
          }
          //}
      }
      if (j) {
        if (dp[i][j] < dp[i][j-1]) {
          dp[i][j] = dp[i][j-1];
          prev[i][j] = prev[i][j-1];
        }
      }
    }
  }

  // REP(i,n) {
  //   REP(j,i+1) cout << dp[i][j] << " ";
  //   cout << endl;
  // }
  
  // REP(i,n) {
  //   REP(j,i+1) cout << v[i][j].first << " ";
  //   cout << endl;
  // }
  pii now = pii(n-1,n-1);
  vector<int> ans;
  while(now.first!=-1) {
    if (now.first != n-1) 
      ans.push_back(now.first);
    int p = prev[now.first][now.second];
    REP(i,n) {
      if (dp[p][i] == dp[now.first][now.second]-1) {
        now = pii(p,i);
        break;
      }
    }
  }
  reverse(ALL(ans));
  cout << dp[n-1][n-1] << endl;
  REP(i,ans.size()) {
    if (i) cout << " ";
    cout << ans[i]+1;
  }
  cout << endl;
}

Measured memory_bytes: 187212
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(10 ** 9)


def main():
    S = input()
    S = S.replace("BC", "X")
    S = S.replace("C", "B")
    S = S.split("B")
    answer = 0
    for s in S:
        place = []
        c = 0
        n = len(s)
        for i in range(n):
            if s[i] == "A":
                c += 1
                place.append(i + 1)
        for p in place:
            c -= 1
            answer += n - c - p
    print(answer)


if __name__ == "__main__":
    main()


Measured memory_bytes: 11368
N, M = map(int, input().split())

plan = []
for _ in range(M):
    a, b = map(int, input().split())
    plan.append([a-1, b-1])

# sort by end point
plan = sorted(plan, key=lambda x:x[1])

e = 0
count = 0
for i in range(M):
    if plan[i][0] >= e:
        e = plan[i][1]
        count += 1
print(count)


Measured memory_bytes: 22108
D, G = [int(i) for i in input().split()]
P, C = [0] * (D + 1), [0] * (D + 1)
for i in range(D):
    P[i + 1], C[i + 1] = [int(i) for i in input().split()]

def solve(d, g):
    if d <= 0:
        return 1e5

    n = min(g // (d * 100), P[d])
    score = (d * 100) * n
    if n == P[d]:
        score += C[d]

    if score < g:
        n += solve(d - 1, g - score)

    return min(n, solve(d - 1, g))

print(solve(D, G))


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

#define pb(n) push_back(n)
#define fi first
#define se second
#define all(r) (r).begin(),(r).end()
#define gsort(st,en) sort((st),(en),greater<int>())
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)
#define vary(type,name,size,init) vector< type> name(size,init)

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using dict = map<string,int>;
using pii = pair<int,int> ;

constexpr int imax = ((1<<30)-1)*2+1 ;
constexpr int inf = 100000000;
constexpr double PI = acos(-1.0) ;
double eps = 1e-10 ;
const int dy[] = {-1,0,1,0};
const int dx[] = {0,-1,0,1};

inline bool value(int x,int y,int w,int h){
  return (x >= 0 && x < w && y >= 0 && y < h);
}

template<typename T>
void Unique(vector<T> &v){
  sort(all(v));
  v.erase(unique(all(v)),v.end());
}

template<typename T>
T ston(string& str, T n){
  istringstream sin(str) ;
  T num ;
  sin >> num ;
  return num ;
}

void Ans(bool f){
  if(f) cout << "YES"<<endl;
  else cout << "NO"<<endl;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n,s,e;
  cin >> n;
  rep(i,n){
    cin >> s >> e;
    if(s + e < 7){
      if(s < e){
        REP(j,s,e){
          cout << j << " ";
        }
        cout << e << endl;
      }
      else{
        for(int j = s; j > e;--j){
          cout << j << " ";
        }
        cout << e << endl;
      }
    }
    else{
      if(s < e){
        REP(j,s,e){
          cout << j << " ";
        }
        cout << e << endl;
      }
      else{
        if(e < 6){
          REP(j,s,10){
            cout << j<< " ";
          }
          rep(j,5-e){
            cout << 5-j<< " ";
          }
          cout << e << endl;
        }
        else{
          REP(j,s,10){
            cout << j<< " ";
          }
          rep(j,5){
            cout << 5-j<< " ";
          }
          rep(j,e){
            cout << j << " ";
          }
          cout << e << endl;
        }
      }
    }
  }
  return 0;
}

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

using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

using Pi = pair<int, int>;
using Ti = tuple<int, int, int>;
using vint = vector<int>;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  string s;
  cin >> s;
  int a[4];
  rep(i, 4) a[i] = s[i]-'0';
  rep(i, 1<<3) {
    int sum = a[0];
    rep(j, 3) {
      if((i>>j)&1) sum += a[j+1];
      else sum -= a[j+1];
    }
    if(sum == 7) {
      cout << a[0];
      rep(j, 3) {
	if((i>>j)&1) cout << '+';
	else cout << '-';
	cout << a[j+1];
      }
      cout << "=7" << endl;
      return 0;
    }
  }

  return 0;
}


Measured memory_bytes: 256
/// kazuki08
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
typedef long long ll;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
//#define inf 1000000000
#define mod 1000000007
#define dmp(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl
#define fs first
#define sc second
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define mt make_tuple
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
    return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
    o<<"{";
    for(const T& v:vc) o<<v<<",";
    o<<"}";
    return o;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int prime(int x){
  for(int i=2;i*i<=x;i++){
    if( x%i==0 )return 0;
  }
  return 1;
}

signed main(){
IOS;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
        
  int a,b,k;
  cin >> a >> b >> k;
  int d = min(a,k);
  a-=d;
  k-=d;
  d = min(k, b);
  b-=d;
  cout<<a << " " << b << endl;    

return 0;
}
///....


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

from collections import deque

def solve():
    N = II()
    E = [[] for _ in range(N)]

    out = []
    for i in range(N-1):
        a, b = MI1()
        E[a].append(b)
        E[b].append(a)
        out.append((a, b))

    q = deque([(0, -1, -1)])
    memo = {}
    max_color = 0
    while len(q) > 0:
        current, v_pre, c_pre = q.popleft()
        color = 1
        for nv in E[current]:
            if nv == v_pre: continue
            if color == c_pre:
                color += 1
            q.append((nv, current, color))
            memo[(min(nv, current), max(nv, current))] = color
            max_color = max(max_color, color)
            color += 1
    # print(memo)

    print(max_color)
    for t in out:
        print(memo[t])

if __name__ == '__main__':
    solve()


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

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

/*********** Constants ***********/
const auto INF = static_cast<ll>(1e15);
const auto MOD = static_cast<ll>(1e9 + 7);

/*********** Variables ***********/
ll N;
vector<ll> A;
vector<vector<ll>> DP;

/*********** Functions ***********/
void initialize() {
    cin >> N;
    A.resize(N);
    for (auto& item : A) cin >> item;
    DP.resize(N + 1, vector<ll>(N + 1, 0));
}

void solve() {
    for (ll len = 1; len <= N; len++) {
        for (ll i = 0; i + len <= N; i++) {
            ll j = i + len;
            if ((N - len) % 2) {
                DP[i][j] = min(DP[i + 1][j] - A[i], DP[i][j - 1] - A[j - 1]);
            }
            else {
                DP[i][j] = max(DP[i + 1][j] + A[i], DP[i][j - 1] + A[j - 1]);
            }
        }
    }
}

void output() {
    cout << DP[0][N] << endl;
}

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


Measured memory_bytes: 70784
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <vector>
//#define MAX_SYMBOL 300//シンボルの最大数
using namespace std;

class SimpleStack{
private	:
	vector<int> v;
public	:

	void put(int n){
		v.push_back(n);
	}

	int pop(){
		int val;
		if(!v.empty()){
			val = *(v.end()-1);
			v.pop_back();
			return val;
		}
	}

};

//&を使って参照渡しにすることでコピーによるメモリ消費を回避できる
//しかも扱いは->でなく.でOK
//http://homepage2.nifty.com/well/Reference.html#PASS_BY_REFERENCE の3
double calc(char q, SimpleStack& ss){
	double a;
	double b;
	if(q == '+'){
		a = ss.pop();
		b = ss.pop();
		ss.put(a + b);
		return a + b;
	}else if(q == '-'){
		a = ss.pop();
		b = ss.pop();
		ss.put(b - a);
		return b - a;//a-bでないことに注意！
	}else if(q == '*'){
		a = ss.pop();
		b = ss.pop();
		ss.put(a * b);
		return a * b;
	}
	return 0;
}

int main(){
	SimpleStack ss;
	char s[100];//1単位
	int num;
	int i = 0;


	while(scanf("%s",s) != EOF){
	
		if(s[0] == '+' || s[0] == '-' || s[0] == '*')calc(s[0],ss);
		else{
			num = atoi(s);
			ss.put(num);
		}
	}
	cout <<ss.pop() <<endl;

	return 0;
}

Measured memory_bytes: 1220
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int T = sc.nextInt();
        for (int i = 0; i < T; i++) {
            new Main().solve(sc, pw);
        }
        pw.flush();
        pw.close();
        sc.close();
    }

    long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    void solve(Scanner sc, PrintWriter pw) {
        long A = sc.nextLong();
        long B = sc.nextLong();
        long C = sc.nextLong();
        long D = sc.nextLong();
        pw.write(solve(A, B, C, D) ? "Yes" : "No");
        pw.write("\n");
    }

    boolean solve(long A, long B, long C, long D) {
        if (A < B) {
            return false;
        }
        long g = gcd(B, D);
        long remainderA = A % B;
        if (remainderA > C) {
            return false;
        }
        long delta = remainderA % g;
        if (g > 1) {
             if (delta + D < B) {
                 return false;
             }
        } else {
            if (D < B) {
                return false;
            }
        }
        long cPlusOne = C - delta;
        long bMinusOne = B - delta;
//        return bMinusOne / g <= cPlusOne / g;
        long candidate =  (cPlusOne + g - 1) / g;
        long candidate2 =  (cPlusOne) / g + 1;
        return !(valide(candidate, g, cPlusOne, bMinusOne) || valide(candidate2, g, cPlusOne, bMinusOne));
    }

    private boolean valide(long candidate2, long g, long cPlusOne, long bMinusOne) {
        long value = candidate2 * g;
        return value > cPlusOne && value < bMinusOne;
    }
}


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

namespace AtCoder
{

    class Program
    {
        static void Main()
        {
            Solve();

            Console.ReadKey();
        }

        static void Solve()
        {
            var cin = GetIntArray();
            var ans = cin[0] % cin[1] == 0 ? 0 : 1;


            Console.WriteLine(ans);
        }

        static public string GetStr() { return Console.ReadLine(); }
        static public int GetInt() { return int.Parse(Console.ReadLine()); }
        static public long GetLong() { return long.Parse(Console.ReadLine()); }
        static public string[] GetStrArray() { return Console.ReadLine().Split(' '); }
        static public int[] GetIntArray() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
        static public long[] GetLongArray() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
        static public List<double> GetDoubleList() { return Console.ReadLine().Split(' ').Select(double.Parse).ToList(); }
        static public void WriteObjects<T>(IEnumerable<T> values) { foreach (var o in values) { Console.Write(o + " "); } }

        static bool eq<T, U>() => typeof(T).Equals(typeof(U));
        static T ct<T, U>(U a) => (T)Convert.ChangeType(a, typeof(T));
        static T cv<T>(string s) => eq<T, int>() ? ct<T, int>(int.Parse(s))
                           : eq<T, long>() ? ct<T, long>(long.Parse(s))
                           : eq<T, double>() ? ct<T, double>(double.Parse(s))
                           : eq<T, char>() ? ct<T, char>(s[0])
                                             : ct<T, string>(s);
        static void Multi<T>(out T a) => a = cv<T>(GetStr());
        static void Multi<T, U>(out T a, out U b)
        {
            var ar = GetStrArray(); a = cv<T>(ar[0]); b = cv<U>(ar[1]);
        }
        static void Multi<T, U, V>(out T a, out U b, out V c)
        {
            var ar = GetStrArray(); a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]);
        }
    }
}

Measured memory_bytes: 13268
// "header" {{{
#pragma GCC optimize("Ofast")

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <tuple>
#include <iomanip>
#include <climits>

using namespace std;

#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int> 
#define int int64_t
#define Fixed fixed << setprecision(10)
#define moke_pair make_pair

constexpr int INF = 0x3f3f3f3f;
constexpr int64_t LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int64_t mod1 = 1000000007;
constexpr int64_t mod2 = 998244353;

constexpr int dx[] = {1,0,-1,0,1,1,-1,-1};
constexpr int dy[] = {0,-1,0,1,1,-1,-1,1};

template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;
template <class T,class U> using umap = unordered_map<T,U>;

inline int64_t updiv(int64_t n,int64_t d){ return ((n + d -1) / d); }
inline int square(int a){ return a * a; }
// }}}

signed main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int h,w;
    cin >> h >> w;

    vector<vector<bool> > wall(h+1,vector<bool>(w+1));
    vector<vector<int> > dp(h+1,vector<int>(w+1));

    reps(i,h){
        reps(j,w){
            char a;
            cin >> a;
            wall[i][j] = (a == '#');
        }
    }

    dp[1][1] = 1;

    reps(i,h){
        reps(j,w){
            if(wall[i][j]) continue;
            (dp[i][j] += dp[i][j-1] + dp[i-1][j]) %= mod1;
        }
    }

    cout << dp[h][w] << '\n';

    return 0;
}


Measured memory_bytes: 8320
import System.Exit
import Control.Applicative

extra :: String -> Int -> Int -> [String]
extra cs a b = [(take (a) cs), (take (b - a + 1) (drop (a) cs)), (drop (b + 1) cs)]

rev :: String -> Int -> Int -> String
rev cs a b = let [pre, mid, pos] = extra cs a b
              in pre ++ (reverse mid) ++ pos

rpl :: String -> Int -> Int -> String -> String
rpl cs a b ns = let [pre, _, pos] = extra cs a b
                 in pre ++ ns ++ pos

prt :: String -> Int -> Int -> String
prt cs a b = let [pre, mid, pos] = extra cs a b
              in mid

main = do
    cs <- getLine
    getLine
    ops <- map words . lines <$> getContents
    solve ops cs

solve :: [[String]] -> String -> IO ()
solve [] _ = exitSuccess
solve ((op:a:b:rest):ops) cs = do
    case op of
        "reverse" -> solve ops (rev cs (read a) (read b))
        "replace" -> solve ops (rpl cs (read a) (read b) (head rest))
        "print"   -> putStrLn (prt cs (read a) (read b)) >> solve ops cs


Measured memory_bytes: 5480
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String line = sc.nextLine();
		String ans = "";

		int len = line.length();
		int i = 0;
		for(i = 0; i < len; i++){
			char ch = line.charAt(i);
			if(Character.isLowerCase(ch)) {
				ch = Character.toUpperCase(ch);

			}else {
				ch = Character.toLowerCase(ch);
			}

			ans = String.valueOf(ch);
			System.out.printf("%s",ans);
		}
		System.out.println("");

		sc.close();
	}
}



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

int n,X[200005],Y[200005];
char D[200005];
vector<pair<int,int>> RP,LP;
map<int,set<int>> RL,LL;
vector<int> LR[200005],RR[200005],UC[200005],DC[200005];

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    for(int i=0;i<n;i++){
        cin>>X[i]>>Y[i]>>D[i];
        int &x=X[i],&y=Y[i];
        char &d=D[i];
        if(d=='U'){
            UC[x].emplace_back(y);
            LL[y-x].insert(y);
            RL[x+y-1919810].insert(y);
        }
        if(d=='D'){
            DC[x].emplace_back(y);
            LL[x+y-1919810].insert(y);
            RL[y-x].insert(y);
        }
        if(d=='R'){
            RR[y].emplace_back(x);
            RP.emplace_back(x,y);
        }
        if(d=='L'){
            LR[y].emplace_back(x);
            LP.emplace_back(x,y);
        }
    }
    int ans=1e9;
    for(int r=0;r<200000;r++){
        sort(LR[r].begin(),LR[r].end());
        LR[r].emplace_back(1919810);
        sort(RR[r].begin(),RR[r].end());
        for(int &x:RR[r]){
            int y=*lower_bound(LR[r].begin(),LR[r].end(),x);
            if(y!=1919810)ans=min(ans,(y-x)*5);
        }
    }
    for(int c=0;c<200000;c++){
        sort(UC[c].begin(),UC[c].end());
        sort(DC[c].begin(),DC[c].end());
        DC[c].emplace_back(1919810);
        for(int &x:UC[c]){
            int y=*lower_bound(DC[c].begin(),DC[c].end(),x);
            if(y!=1919810)ans=min(ans,(y-x)*5);
        }
    }
    for(pair<int,int> &px:RP){
        int y;
        if(RL.find(px.second-px.first)!=RL.end() && RL[px.second-px.first].lower_bound(px.second)!=RL[px.second-px.first].end()){
            y=*RL[px.second-px.first].lower_bound(px.second);
            ans=min(ans,(y-px.second)*10);
        }
        if(RL.find(px.second+px.first-1919810)!=RL.end() && RL[px.second+px.first-1919810].upper_bound(px.second)!=RL[px.second+px.first-1919810].begin()){
            y=*(--RL[px.second+px.first-1919810].upper_bound(px.second));
            ans=min(ans,(px.second-y)*10);
        }
    }
    for(pair<int,int> &px:LP){
        int y;
        if(LL.find(px.second-px.first)!=LL.end() && LL[px.second-px.first].upper_bound(px.second)!=LL[px.second-px.first].begin()){
            y=*(--LL[px.second-px.first].upper_bound(px.second));
            ans=min(ans,(px.second-y)*10);
        }
        if(LL.find(px.second+px.first-1919810)!=LL.end() && LL[px.second+px.first-1919810].lower_bound(px.second)!=LL[px.second+px.first-1919810].end()){
            y=*LL[px.second+px.first-1919810].lower_bound(px.second);
            ans=min(ans,(y-px.second)*10);
        }
    }
    if(ans==1e9)cout<<"SAFE";
    else cout<<ans;

    return 0;
}

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

typedef long long ll;
const int INF = 1e9;
const ll LINF = 1e18;
const int mod = 1e9+7;

#define pi pair<int,int>
#define pl pair<lld,lld>

#define dump(x) cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define SANKOU(n,a,b) cout << ((n) ? (#a) : (#b) ) << endl

#define mem0(x) memset(x,0,sizeof(x))
#define fillnum(x,n) fill(begin(x),end(x),n)
#define asort(x) sort(x.begin(),x.end())
#define dsort(x,t) sort(x.begin(),x.end(),greater<t>())
#define vuniq(x) x.erase(unique(x.begin(), x.end()), x.end())

#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)

int main() {
    string s;
    bool flg[4];
    mem0(flg);
    cin >> s;
    for (int i = 0; i < s.size(); i++) {
        if(s[i] == 'N'){
            flg[0] = true;
        } else if(s[i] == 'W'){
            flg[1] = true;
        } else if(s[i] == 'S'){
            flg[2] = true;
        } else {
            flg[3] = true;
        }
    }
    bool ans = true;
    if(flg[0] != flg[2]){
        ans = false;
    }
    if(flg[1] != flg[3]){
        ans = false;
    }
    Yes(ans);
}

Measured memory_bytes: 3604
#include<iostream>
#include<cstdio>
#include <string.h>
using namespace std;

int main() {
    int a, b, c, d, e, f, g, h;
    cin >> a >> b;
    
       
            d = a * (a - 1);
            f = d / 2;
            e = b * (b - 1);
            g = e / 2;
            h = f + g;
            cout << h;
    
}


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

int main(){
  string S;
  cin>>S;
  int N=S.length();
  int NN=0;
  int NS=0;
  int NE=0;
  int NW=0;
  for (int i=0;i<N;i++){
    if(S.at(i)=='N'){
      NN++;
    }
      if(S.at(i)=='S'){
      NS++;
      }
        if(S.at(i)=='W'){
      NW++;
    }
        if(S.at(i)=='E'){
      NE++;
    }
  }
  if((NN>0)&&(NS==0)){
    cout<<"No"<<endl;
    return 0;
  }
  if((NN==0)&&(NS>0)){
    cout<<"No"<<endl;
    return 0;
  }
  if((NE>0)&&(NW==0)){
    cout<<"No"<<endl;
    return 0;
  }
  if((NE==0)&&(NW>0)){
    cout<<"No"<<endl;
    return 0;
  }
  cout<<"Yes"<<endl;
  return 0;
}

    

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <fstream>
#include <bitset>
#include <queue>
#include <stack>
#include <deque>
#include <complex>
#include <iomanip>
#include <stdio.h>
#include <string.h>

using std::cin;
using std::cout;
using std::cerr;
using std::endl;

using std::map;
using std::set;
using std::bitset;
using std::vector;
using std::string;
using std::multimap;
using std::multiset;
using std::deque;
using std::queue;
using std::stack;
using std::pair;
using std::iterator;

using std::sort;
using std::stable_sort;
using std::reverse;
using std::max_element;
using std::min_element;
using std::unique;
using std::ios_base;
using std::swap;
using std::fill;

using std::setprecision;
using std::fixed;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef string S;

ll min(ll a, ll b) {return a < b ? a : b;}
ll min(int a, ll b) {return a < b ? a : b;}
ll min(ll a, int b) {return a < b ? a : b;}
ll min(int a, int b) {return a < b ? a : b;}

ll max(ll a, ll b) {return a > b ? a : b;}
ll max(int a, ll b) {return a > b ? a : b;}
ll max(ll a, int b) {return a > b ? a : b;}
ll max(int a, int b) {return a > b ? a : b;}

namespace MySpace{

};

#define F(i, n) for (int (i) = 0; (i) != (n); (i)++)
#define fi first
#define se second
#define re return
#define all(x) (x).begin(), (x).end()

ll n, m;

ll d[1001][1001];
ll p[1001][1001];

signed main()
{
    srand(time(NULL));
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    F(i, 1001) F(j, 1001) d[i][j] = 1e9;
    F(i, m)
    {
        int v, u;
        cin >> v >> u;
        d[v][u] = 1;
        p[v][u] = v;
    }
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (d[i][k] + d[k][j] < d[i][j])
                {
                    d[i][j] = d[i][k] + d[k][j];
                    p[i][j] = p[k][j];
                }
            }
        }
    }
    int mind = 1e9;
    for (int i = 1; i <= n; i++)
    {
        mind = min(mind, d[i][i]);
    }
    if (mind == 1e9)
    {
        cout << "-1";
        re 0;
    }
    for (int i = 1; i <= n; i++)
    {
        if (d[i][i] == mind)
        {
            int p0 = p[i][i];
            vector<int> v = {i};
            while (p0 != i)
            {
                v.push_back(p0);
                p0 = p[i][p0];
            }
            cout << v.size() << endl;
            for (int i = 0; i < v.size(); i++) cout << v[i] << "\n";
            re 0;
        }
    }
}


Measured memory_bytes: 15872
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
lh, lw = map(int, input().split())
tizu = [input() for _ in range(h)]

inf = 10 ** 9
check = [[inf for _ in range(w)] for _ in range(h)]
queue = deque()
ch -= 1
cw -= 1
lh -= 1
lw -= 1
walk = [[-1, 0], [1, 0], [0, 1], [0, -1]]

queue.append([ch, cw])
d = 0

while queue:
    queue2 = queue.copy()
    queue = deque()
    while queue2:
        pos = queue2.popleft()
        flg = [False, False, False, False]
        for dh, dw in walk:
            n_h = pos[0] + dh
            n_w = pos[1] + dw
            if n_h == -1 or n_w == -1 or n_h == h or n_w == w:
                continue
            if tizu[n_h][n_w] == "#":
                if dh == 1:
                    flg[0] = True
                elif dh == -1:
                    flg[1] = True
                elif dw == 1:
                    flg[2] = True
                else:
                    flg[3] = True
                continue
            if check[n_h][n_w] <= d:
                continue
            check[n_h][n_w] = d
            queue2.append([n_h, n_w])
            
        magic = []
        if flg[0]:
            magic.append([2, 0])
            if flg[2]:
                magic.append([2, 1])
                magic.append([2, 2])
                magic.append([1, 2])
                magic.append([1, 1])
            if flg[3]:
                magic.append([2, -1])
                magic.append([2, -2])
                magic.append([1, -2])
                magic.append([1, -1])
        if flg[1]:
            magic.append([-2, 0])
            if flg[2]:
                magic.append([-2, 1])
                magic.append([-2, 2])
                magic.append([-1, 2])
                magic.append([-1, 1])
            if flg[3]:
                magic.append([-2, -1])
                magic.append([-2, -2])
                magic.append([-1, -2])
                magic.append([-1, -1])
        if flg[2]:
            magic.append([0, 2])
        if flg[3]:
            magic.append([0, -2])
            
        for dh, dw in magic:
            n_h = pos[0] + dh
            n_w = pos[1] + dw
            if n_h == -1 or n_w == -1 or n_h == h or n_w == w:
                continue
            if tizu[n_h][n_w] == "#":
                continue
            if check[n_h][n_w] <= d + 1:
                continue
            check[n_h][n_w] = d + 1
            queue.append([n_h, n_w])
    d += 1

if check[lh][lw] == inf:
    print(-1)
else:
    print(check[lh][lw])


Measured memory_bytes: 113212
package main

import "fmt"

func main() {
	var s string
	fmt.Scan(&s)

	len := len(s)
	var f, l int
	for i := 0; i < len-1; i++ {
		if s[i] == 'A' {
			f = i
			break
		}
	}
	for j := len - 1; j > 0; j-- {
		if s[j] == 'Z' {
			l = j
			break
		}
	}

	fmt.Println(l - f + 1)
}


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


int main (){
    int N, T;
    cin>>N>>T;
    vector<int> Cost(N), Time(N);
    for(int i=0; i<N; i++){
        cin>>Cost.at(i)>>Time.at(i);
    }
    int LowestCost=9999;
    for(int i=0; i<N; i++){
        if(T+1>Time.at(i)){
            LowestCost=min(LowestCost, Cost.at(i));

        }
    }
    if(LowestCost==9999){
        cout<<"TLE"<<endl;
    }
    else{
        cout<<LowestCost<<endl;
    }
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque, Counter
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math

def main():
    n = getN()
    parity = n % 2
    if parity == 1:
        print(0)
        return
    ans = 0

    tmp = 5
    while(tmp <= n):
        rep = n // tmp
        ans += (rep + parity) // 2
        tmp *= 5

    print(ans)

if __name__ == "__main__":
    main()



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

#define REP(i,m,n) for(int i=(m); i<(int)(n); i++)
#define RREP(i,m,n) for(int i=(int)(n-1); i>=m; i--)
#define rep(i,n) REP(i,0,n)
#define rrep(i,n) RREP(i,0,n)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aut(r,v) __typeof(v) r = (v)
#define each(it,o) for(aut(it,(o).begin()); it!=(o).end(); ++it)
#define reach(it,o) for(aut(it,(o).rbegin()); it!=(o).rend(); ++it)
#define fi first
#define se second
#define debug(...) {cerr<<"[L"<<__LINE__<<"] "; _debug(__VA_ARGS__);}

template<typename T1, typename T2> ostream& operator<<(ostream& o, const pair<T1, T2>& p)
{return o<<"("<<p.first<<", "<<p.second<<")";}
template<typename T>string join(const vector<T>&v, string del=", ")
{stringstream s;rep(i,v.size())s<<del<<v[i];return s.str().substr(del.size());}
template<typename T>ostream& operator<<(ostream& o, const vector<T>&v)
{if(v.size())o<<"["<<join(v)<<"]";return o;}
template<typename T>ostream& operator<<(ostream& o, const vector<vector<T> >&vv)
{int l=vv.size();if(l){o<<endl;rep(i,l){o<<(i==0?"[ ":",\n  ")<<vv[i]<<(i==l-1?" ]":"");}}return o;}
template<typename T>ostream& operator<<(ostream& o, const set<T>& st)
{vector<T> v(st.begin(),st.end());o<<"{ "<<join(v)<<" }";return o;}
template<typename T1, typename T2>ostream& operator<<(ostream& o, const map<T1, T2>& m)
{each(p,m){o<<(p==m.begin()?"{ ":",\n  ")<<*p<<(p==--m.end()?" }":"");}return o;}
inline void _debug(){cerr<<endl;}
template<class First, class... Rest>
void _debug(const First& first, const Rest&... rest){cerr<<first<<" ";_debug(rest...);}

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;

const double PI = (1*acos(0.0));
const double EPS = 1e-9;
const ll INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
const ll mod = 1e9 + 7;

inline void finput(string filename) {
    freopen(filename.c_str(), "r", stdin);
}

template<typename T>
struct BIT{
    int N;
    vector<T> dat;
    BIT(){}
    BIT(int n) : N(n), dat(n+1,0){ }
    void add(int i, T num){
        for(int x = i+1; x <= N; x += (x & -x)) dat[x] += num;
    }
    T sum(int i){
        T ret = 0;
        for(int x = i+1; x > 0; x -= (x & -x)) ret += dat[x];
        return ret;
    }
    T sum(int i, int j){
        return sum(j) - sum(i-1);
    }
};

vl A;
vvl dp;
BIT<ll> bit;

ll rec(int l, int r){
    if(l == r) return 0;
    if(dp[l][r] != INFL) return dp[l][r];
    ll ret = INFL;
    REP(i,l,r){
        ret = min(ret, (rec(l,i) + rec(i+1,r) + bit.sum(l,r)));
    }
    return dp[l][r] = ret;
}

int main(){
    ios_base::sync_with_stdio(0);
    // finput("./input");

    int n; cin >> n;
    A = vl(n);
    rep(i,n) cin >> A[i];
    dp = vvl(n, vl(n, INFL));
    bit = BIT<ll>(n+1);
    rep(i,n) bit.add(i, A[i]);

    cout << rec(0,n-1) << endl;
    return 0;
}

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

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { std::cout << #a << " = " << a << "\n"; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }
template<class T, class V> istream& operator>> (istream& ist, pair<T, V>& p) { return ist >> p.first >> p.second; }
template<class T> ostream& operator<< (ostream& ost, pair<T, T>& p) { return ost << p.first << ", " << p.second; }
template<class T> istream& operator>> (istream& ist, vector<T>& vs) { for(auto& e: vs) ist >> e; return ist; }

typedef long long ll;
int const inf = 1<<29;

int main() {
  int K; cin >> K;
  cout << K / 2 * ((K + 1) / 2) << "\n";
}


Measured memory_bytes: 256
from collections import defaultdict

INF = 999999999999999999999

def dijkstra(G, s):
  heap = Heap()
  heap.push((s, 0))
  fixed = set()
  d = defaultdict(lambda: INF)
  d[s] = 0
  while len(heap.data) > 0:
    v = heap.pop()
    if v in fixed:
      continue
    for u in G[v]:
      if u in fixed:
        continue
      c = G[v][u]
      if d[v] + c < d[u]:
        d[u] = d[v] + c
        heap.push((u, d[u]))
    fixed.add(v)
  return d


class Heap:
  def __init__(self):
    self.data = []

  def push(self,x):
    self.data.append(x)
    i = len(self.data)-1
    while self._p(i) >= 0:
      if self.data[i][1] < self.data[self._p(i)][1]:
        tmp = self.data[i]
        self.data[i] = self.data[self._p(i)]
        self.data[self._p(i)] = tmp
        i = self._p(i)
      else:
        break

  def pop(self):
    ret = self.top()
    n = self.data.pop()
    if len(self.data) > 0:
      self.data[0] = n
      i = 0
      while True:
        if self._l(i) < len(self.data):
          l = self.data[self._l(i)]
        else:
          l = (-1, INF)
        if self._r(i) < len(self.data):
          r = self.data[self._r(i)]
        else:
          r = (-1, INF)
        if l[1] > r[1]:
          if r[1] < self.data[i][1]:
            tmp = self.data[i]
            self.data[i] = self.data[self._r(i)]
            self.data[self._r(i)] = tmp
            i = self._r(i)
          else:
            break
        else:
          if l[1] < self.data[i][1]:
            tmp = self.data[i]
            self.data[i] = self.data[self._l(i)]
            self.data[self._l(i)] = tmp
            i = self._l(i)
          else:
            break
    return ret[0]

  def top(self):
    return self.data[0]

  def _p(self, i):
    i = i+1
    return i//2-1

  def _l(self, i):
    i = i+1
    return i*2-1

  def _r(self, i):
    i = i+1
    return i*2


G = {}

n, m, r = [int(v) for v in input().strip().split(' ')]
for i in range(n):
  G[i] = {}
for _ in range(m):
  s, t, c = [int(v) for v in input().strip().split(' ')]
  G[s][t] = c

d = dijkstra(G, r)

for i in range(n):
  if d[i] == INF:
    print("INF")
  else:
    print(d[i])

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

int main() {
  string str;
  cin >> str;

  vector<int> m(str.size()), n(str.size());
  
  for( int i = 0; i < str.size(); ++i ) {
    m[i] = 9;
    n[i] = 1;
  }
  
  for( int i = 0; i < ( str.size() - 1 ); ++i ) {
    if( str[i] == 'R' && str[i+1] == 'L' ) {
      m[i] = 0;
      m[i+1] = 0;
    }
  }
  
  for( int i = 0; i < str.size(); ++i ) {
    if( m[i] != 0 ) {
      if( str[i] == 'R' ) {
        m[i] = 1;
      }
      else {
        m[i] = -1;
      }
    }
  }
  
  for( int i = 0; i < str.size(); ++i ) {

    if( m[i] == 0 ){
      for( int j = 1; ( (i-j) > -1 && m[i-j] == 1 ); ++j ) {
        if( j % 2 == 1 ) {
          --n[i-j];
          ++n[i+1];
        }
        else {
          --n[i-j];
          ++n[i];
        }
      }
    
      for( int j = 2; ( (i+j) < str.size() && m[i+j] == -1 ); ++j ) {
        if( j % 2 == 1 ) {
          --n[i+j];
          ++n[i+1];
        }
        else {
          --n[i+j];
          ++n[i];
        }
      }
      
      ++i;
    }
  }
  
  for( int i = 0; i < ( str.size() - 1 ); ++i ) {
    cout << n[i] << " ";
  }
  cout << n[(str.size() - 1)] << endl;
  
  return 0;
}

Measured memory_bytes: 1408