akhauriyash/Code-Regression huggingface dataset:
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<list>
#include<bitset>
#include<stack>
#include<memory>
#include<numeric>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);*/
const int mod=1000000007 ;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-10;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(const vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(const vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}

int main(void){
	cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);
	int n,i;cin>>n;
	llint L;cin>>L;
	vector<pair<llint,llint>>dri(n);//通常の登り,ピーク登り
	vector<llint>c(n+1);//相手
	for(i=0;i<n;i++){llint AA,BB;cin>>AA>>BB;dri[i]=mp(AA-BB,AA);}
	for(i=0;i<n;i++){cin>>c[i+1];c[i+1]+=c[i];}
	SO(dri);REV(dri);
	vector<llint>wa(n+1);
	for(i=0;i<n;i++){wa[i+1]=wa[i]+max(0LL,dri[i].fir);}
	vector<llint>yorui(n+1);
	yorui[0]=big;yorui[1]=big;
	for(i=2;i<=n;i++){yorui[i]=wa[i]-c[i-1];mineq(yorui[i],yorui[i-1]);}
	llint usedD=-big;
	int outm=1,ans=mod;
	while(outm<n&&wa[outm]>c[outm]){outm++;}
	//cerr<<"outm="<<outm<<endl;
	//for(i=0;i<n;i++){cerr<<yorui[i]<<" ";}cerr<<endl;
	for(i=n-1;i>=0;i--){
		
		if(!maxeq(usedD,dri[i].sec)){continue;}
		//最終日使用ドリンク
		llint Lg=L-dri[i].sec;
		//cerr<<"Lg="<<Lg<<endl;
		if(wa[i]>=Lg){//それまでに普通に足りている
			int bas=LBI(wa,Lg);
			//cerr<<"i="<<i<<"bass="<<bas<<endl;
			if(bas<outm){mineq(ans,bas+1);}
		}else{
			if(outm<=i){continue;}
			int bas=LBI(wa,Lg+max(0LL,dri[i].fir));
			if(bas==n+1){continue;}
			//cerr<<"i="<<i<<"bas="<<bas<<endl;
			if(yorui[bas]>dri[i].fir){mineq(ans,bas);}
		}
	}
	if(ans==mod){ans=-1;}
	cout<<ans<<endl;
	return 0;
}
/*
7 10
4 7
1 6
-3 4
-4 10
*/


Measured memory_bytes: 6788
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		String O = in.nextLine();
		String E = in.nextLine();
		String pass = "";
		for (int x = 0; x < O.length(); x++) {
			pass += String.valueOf(O.charAt(x));
			if (x == E.length()) {
				break;
			} else {
				pass += String.valueOf(E.charAt(x));
			}
		}
		System.out.println(pass);
	}

}


Measured memory_bytes: 23764
#include <iostream>
using namespace std;
  
void PrintCheckFirstSharp (int length) {
  for ( int i = 0; i < length; ++i) {
    if ( i % 2 == 0 ) {
      cout << '#';
    } else {
      cout << '.';
    }
  }
  cout << endl;
}
  
void PrintCheckFirstDot ( int length ) {
  for ( int i = 0; i < length; ++i ){
    if ( i % 2 == 0 ) {
      cout << '.';
    } else {
      cout << '#';
    }
  }
  cout << endl;
}
  
void PrintArea( int H, int W ) {
  for ( int i = 0; i < H; ++i ) {
    if ( i % 2 == 0 ) {
      PrintCheckFirstSharp( W );
    } else {
      PrintCheckFirstDot( W );
    }
  }
  cout << endl;
}
  
int main() {
  while (true) {
    int H, W;
    cin >> H >> W;
    if (H == 0 && W == 0) break;
    PrintArea(H, W);
  }
  return 0;
};

Measured memory_bytes: 1152
import java.util.Arrays;

public class Main {


  private static void solve() {
    int[] a = na(3);
    Arrays.sort(a);
    System.out.println(a[0] + a[1]);
  }

  public static void main(String[] args) {
    new Thread(null, new Runnable() {
      @Override
      public void run() {
        long start = System.currentTimeMillis();
        String debug = args.length > 0 ? args[0] : null;
        if (debug != null) {
          try {
            is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug));
          } catch (Exception e) {
            throw new RuntimeException(e);
          }
        }
        reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768);
        solve();
        out.flush();
        tr((System.currentTimeMillis() - start) + "ms");
      }
    }, "", 64000000).start();
  }

  private static java.io.InputStream is = System.in;
  private static java.io.PrintWriter out = new java.io.PrintWriter(System.out);
  private static java.util.StringTokenizer tokenizer = null;
  private static java.io.BufferedReader reader;

  public static String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }

  private static double nd() {
    return Double.parseDouble(next());
  }

  private static long nl() {
    return Long.parseLong(next());
  }

  private static int[] na(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
      a[i] = ni();
    return a;
  }

  private static char[] ns() {
    return next().toCharArray();
  }

  private static long[] nal(int n) {
    long[] a = new long[n];
    for (int i = 0; i < n; i++)
      a[i] = nl();
    return a;
  }

  private static int[][] ntable(int n, int m) {
    int[][] table = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[i][j] = ni();
      }
    }
    return table;
  }

  private static int[][] nlist(int n, int m) {
    int[][] table = new int[m][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[j][i] = ni();
      }
    }
    return table;
  }

  private static int ni() {
    return Integer.parseInt(next());
  }

  private static void tr(Object... o) {
    if (is != System.in)
      System.out.println(java.util.Arrays.deepToString(o));
  }
}


Measured memory_bytes: 22740
#include<bits/stdc++.h>
using namespace std;
////////////////////
int main() {
    int A,B,C;
    cin >> A >> B >> C;
    int jp[100] = { 0 };
    jp[5] = 2; jp[7] = 1;
    jp[A]--;jp[B]--;jp[C]--;
    
    if(jp[5] == 0 & jp[7] == 0) {
        cout << "YES";
    } else {
        cout << "NO";
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<stdio.h>
#include<algorithm>
#include<string>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll tree[100001],n,m,a[100001],b[100001],t1,t2,d[100001];
pair<ll,ll>c[100001];
ll quyu(ll aa,ll bb)
{
	return (aa+bb)%mod;//防止aa+bb超过mod 
}
void add(ll under,ll v)
{
	for(;under<=n;under+=under&-under)tree[under]=quyu(tree[under],v);//用quyu函数，防超mod 
}
ll sum(ll x)
{
	ll ans=0;
	for(;x;x-=x&-x)ans=quyu(ans,tree[x]);//同上 
	return ans;
}
bool cmp(pair<ll,ll>one,pair<ll,ll>two)//先比较到左边EXIT的距离，再比到右边EXIT的距离。
{
	if(one.first!=two.first)return one.first<two.first; 
	return one.second>two.second;
}
int main()
{
	scanf("%lld %lld",&n,&m);
	for(ll u=1;u<=n;u++)
		scanf("%lld",&a[u]);
	for(ll u=1;u<=m;u++)
		scanf("%lld",&b[u]);
	for(ll u=1;u<=n;u++)
		if(a[u]<b[m]&&a[u]>b[1])//除去在第一个EXIT左边的和最后一个EXIT右边的 
		{
			int xia=lower_bound(b+1,b+m+1,a[u])-b;
			if(a[u]==b[xia])continue;//在EXIT中的不管。 
			c[++t1]=make_pair(a[u]-b[xia-1],b[xia]-a[u]);//存到左边EXIT和到右边EXIT的距离和 
			d[++t2]=b[xia]-a[u];//单纯记录到右边EXIT的距离 
		}
	sort(d+1,d+t2+1);
	t2=unique(d+1,d+t2+1)-d-1;//排序再去重 
	for(ll u=1;u<=t1;u++)
		c[u].second=lower_bound(d+1,d+t2+1,c[u].second)-d;
	sort(c+1,c+t1+1,cmp);
	t1=unique(c+1,c+t1+1)-c-1;//同上 
	ll ans=1;
	for(ll u=1;u<=t1;u++)//维护树状数组 
	{
		ll s=sum(c[u].second-1)+1;//记得+1 
		ans+=s;//累加 
		add(c[u].second,s);//插入 
	}
	ans%=mod;
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 4864
#include<stdio.h>
#define Num 100

int main(){

    int i,j,n;
    int count = 0;
    int mj,stock;
    int a[Num];

    scanf("%d",&n);

    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
    }

    for(i=0;i<n;i++){
        mj = i;
        for(j=i;j<n;j++){
            if(a[j]<a[mj])
            mj = j;
        }
        if(i != mj){
            stock = a[i];
            a[i] = a[mj];
            a[mj] = stock;
            count++;
        }
    }

    for(i=0;i<n;i++){
        if(i != n && i != 0){
            printf(" ");
        }

        printf("%d",a[i]);

    }

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

    return 0;
}


Measured memory_bytes: 2144
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
MOD = 10**9 + 7
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    n, k = LI()

    if n <= k:
        ans = 1
    else:
        ans = 0

    print(ans)

if __name__ == '__main__':
    resolve()



Measured memory_bytes: 6808
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using vi = vector<i64>;
using vvi = vector<vi>;

int main() {
    int w, a, b;
    cin >> w >> a >> b;
    if (a + w < b) {
        cout << b - a - w << endl;
        return 0;
    }
    if (b + w < a) {
        cout << a - b - w << endl;
        return 0;
    }
    cout << 0 << endl;
}

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

#include <algorithm>
#include <array>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <limits>
#include <numeric>
#include <vector>

using namespace std;

#define ll long long
#define ld long double
#define P pair<ll, ll>
#define FOR(i, n, m) for (ll i = n; i < (ll)m; i++)
#define FORr(i, m, n) for (ll i = n; i >= (ll)m; i--)
#define FORm(i, m) for (auto i = m.begin(); i != m.end(); i++)
#define sortAl(v) sort(v.begin(), v.end())
#define sortAlr(v)          \
  sort(v.begin(), v.end()); \
  reverse(v.begin(), v.end())
#define cout(n) cout << fixed << setprecision(n)

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

  vector<ll> a(N);
  FOR(i, 0, N) { cin >> a[i]; }

  ll sum = 0;
  FOR(i, 0, N) { sum += a[i] - 1; }

  cout << sum << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define TR(X) ({ if(1) cerr << "Trace: " << (#X) << " = " << (X) << endl; })
const int P = 1e9 + 7;
const int maxs = 105;
const int amount_digits = 10001;
int dp[amount_digits][maxs][2];

void add_self(int &a, int b) {
	a += b;
	if(a >= P) a -= P;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	string k;
	int d;
	cin >> k >> d;
	int n = (int) k.size();
	dp[0][0][0] = 1;
	for(int digits = 0; digits < n; digits++) {
		for(int cur_sum = 0; cur_sum < d; cur_sum++) for(int smaller = 0; smaller < 2; smaller++) {
			for(int ndigit = 0; ndigit < 10; ndigit++) {
				if(!smaller && ndigit > k[digits] - '0') break;
				int nsmaller = smaller || ndigit < k[digits] - '0';
				add_self(dp[digits + 1][(cur_sum + ndigit) % d][nsmaller], dp[digits][cur_sum][smaller]);
			}
		}
	}
	TR(dp[n][0][0]);
	cout << (dp[n][0][0] + dp[n][0][1] + P - 1) % P << '\n';
}


Measured memory_bytes: 8448
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 998244353

string S;
map<string, int> memo;
int f(string S) {
  if (memo.find(S) != memo.end()) return memo[S];
  int s = ((S[0]-'0')+1)*f(S.substr(1));
  for (int k=1; 2*k<=S.length(); k++) {
    string p(k, '1');
    rep(i, k) if (S[i] == '0') p[i] = '0';
    for (int t=k; t+k<=S.length(); t+=k) {
      rep(i, k) if (S[t+i] == '0') p[i] = '0';
      s = (s + 1LL*f(p)*f(S.substr(t+k))) % MOD;
    }
  }
  return memo[S] = s;
}
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  memo[""] = 1;
  cin >> S;
  cout << f(S) << "\n";
  return 0;
}


Measured memory_bytes: 5632
#include <cstdio>
#include <algorithm>
#include <limits>
#include <numeric>
#include <type_traits>
#include <iostream>

typedef long long ll;
typedef long long int lli;

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

template<class T>bool umax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool umin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

using namespace std;

int v[200000],a[200000]={0},b[200000]={0};
int main() {
    int N ,mem_a=0, mem_b=0;
    cin>> N;

    for(int i=0; i<N; i=i+2){
        cin >> v[i] >> v[i+1];
        a[v[i]]++;
        b[v[i+1]]++;
    }

    int Max_a = 0;
    for(int i=0; i<100005; i++){
        if(Max_a<a[i]) {
            Max_a = a[i];
            mem_a=i;
        }
    }

    int Max_b = 0;
    for(int i=0; i<100005; i++){
        if(Max_b<b[i]) {
            Max_b = b[i];
            mem_b=i;
        }
    }

    int Sec_a = 0;
    a[mem_a]=0;
    for(int i=0; i<100005; i++){
        if(Sec_a<a[i]) {
            Sec_a = a[i];
        }
    }

    int Sec_b = 0;
    b[mem_b]=0;
    for(int i=0; i<100005; i++){
        if(Sec_b<b[i]) {
            Sec_b = b[i];
        }
    }

    int ans=0;
    if(mem_a==mem_b) {
        ans = min(N-Sec_a-Max_b, N-Sec_b-Max_a);
    }else{
        ans = N - Max_a - Max_b;
    }

    printf("%d", ans);
    return 0;

}


Measured memory_bytes: 1408
#include <algorithm>
#include <bitset>
#include <iomanip>
#include <ios>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>

using namespace std;

int main()
{
    string a, b, c;
    cin >> a >> b >> c;
    char x = a[0] - 32;
    char y = b[0] - 32;
    char z = c[0] - 32;
    cout << x << y << z << "\n";
}

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

int main(){
    int N, A;
    cin >> N >> A;

    int div = N/ 500;
    if(N - div*500 <= A){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

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

using namespace std;
typedef long long ll;

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

ll A, B, C, D;
ll ans = 0;
ll LCM;

ll calc(ll x) {
	ll ans = 0;
	ans += (x / LCM) * (LCM - LCM / C - LCM / D + 1);
	ans += (x - x / LCM * LCM) - ((x - x / LCM*LCM) / C + (x - x / LCM * LCM) / D);
	return ans;
}

int main() {
	
	cin >> A >> B >> C >> D;
	LCM = C * D / gcd(C, D);

	cout << calc(B) - calc(A - 1) << endl;

	return 0;
}

Measured memory_bytes: 256
import sys

from collections import deque

def LI():
	return [ int(s) for s in input().split() ]

N,K =LI()
tree = {}
for i in range(N):
  tree[i] = []

MOD = (10**9)+7
color = K

for _ in range(N-1):
    a,b = LI()
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
    

## bfs ###
search_candidate = deque([0])
visited = [False]*N
hierarchy = [-1]*N
hierarchy[0] = 1
for t in tree[0]:
    if t != 0:
        hierarchy[t] = 2

while search_candidate:
    search = search_candidate.pop()
    if hierarchy[search] == 1:
        cnt = K - 1
    else:
        cnt = K - 2
    visited[search] = True
    
    for child in tree[search]:
        if visited[child]:
            continue 

        if cnt <= 0:
            print(0)
            sys.exit()

        color = (color*cnt) % MOD
        cnt -= 1
        search_candidate.appendleft(child)

print(color)

Measured memory_bytes: 33252
#include<iostream>
#include<cstdio>
#include<math.h>
#include<vector>
#include<map>
#include<utility>
#include<algorithm>
#include<string>
using namespace std;
typedef long long ll;

int main(){
    ll N,K;
    ll index;//はじめに1が存在する位置
    ll now;
    ll ans=0;
    ll z1=0;
    ll z2=0;
    vector<ll> a;
    cin>>N>>K;
    for(ll i=0;i<N;i++){
        ll x;
        cin>>x;
        if (x==1){
            index=i;
            now=i;
        }
        a.push_back(x);
    }
    while (now!=a.size()-1){//右側を1に
        now+=K-1;
        if (now<=a.size()-1){
            ans++;
        }else{
            now-=K-1;
            z1=a.size()-1-now;
            break;
        }
    }
    now=index;
    while (now!=0){//左側を1に
        now-=K-1;
        if (now>=0){
            ans++;
        }else{
            now+=K-1;
            z2=now;
            break;
        }
    }
    ll remain=z1+z2;
    if (remain==0){

    }else if (remain<=K-1){
        ans++;
    }else{
        ans+=2;
    }
    cout<<ans<<'\n';
}

Measured memory_bytes: 1400
#include <bits/stdc++.h>
#define f(i,j,k) for(int i=j;i<k;i++)
#define f2(i,j,k) for(int i=j;i>k;i--)
using namespace std;
int main(){
    long long a,b,c,f;
    cin>>a>>b>>c;
    f=a;
    vector <long long> d(b,0);
    while(d[f%b]==0){
        d[f%b]++;
        f+=a;
    }
    if(d[c]==0){
        cout<<"NO"<<endl;
    }
    else{
        cout<<"YES"<<endl;
    }
    return 0;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MOD 1000000007
#define MAX_N 100000
#define MAX_P 200005
int fact[MAX_P];
int extgcd(int a,int b,int& x,int& y){
  int d=a;
  if(b!=0){
    d=extgcd(b,a%b,y,x);
    y-=(a/b)*x;
  }else{
    x=1;y=0;
  }
  return d;
}
int mod_inverse(int a,int m){
  int x,y;
  extgcd(a,m,x,y);
  return (m+x%m)%m;
}

int euler_phi(int n){
  int res=n;
  for(int i=2;i*i<=n;i++){
    if(n%i==0){
      res=res/i*(i-1);
      for(;n%i==0;n/=i);
    }
  }
  if(n!=1) res=res/n*(n-1);
  return res;
}

int euler[MAX_N];

void euler_phi2(){
  for(int i=0;i<MAX_N;i++) euler[i]=i;
  for(int i=2;i<MAX_N;i++){
    if(euler[i]==i){
      for(int j=i;j<MAX_N;j+=i) euler[j]=euler[j]/i*(i-1);
    }
  }
}

int mod_pow(int x,int n,int mod){
  int res=1;
  while(n>0){
    if(n&1) (res*=x)%=mod;
    (x*=x)%=mod;
    n>>=1;
  }
  return res;
}

void init(int p){
  fact[0]=1;
  for(int i=1;i<MAX_P;i++) fact[i]=(fact[i-1]*i)%p;
}

int mod_fact(int n,int p,int& e){
  e=0;
  if(n==0) return 1;
  int res=mod_fact(n/p,p,e);
  e+=n/p;
  if(n/p%2!=0)return res*(p-fact[n%p]) %p;
  return res*fact[n%p]%p;
} 
int mod_comb(int n,int k,int p){
  if(n==k||k==0) return 1;
  int e1,e2,e3;
  int a1=mod_fact(n,p,e1),a2=mod_fact(k,p,e2),a3=mod_fact(n-k,p,e3);
  if(e1>e2+e3) return 0;
  return a1*mod_inverse(a2*a3%p,p)%p;
}

signed main(){
  int a,b;
  cin>>a>>b;
  int x,y;
  extgcd(a,b,x,y);
  cout<<x<<" "<<y<<endl;
  return 0;
}

/*
verified on 2017/04/28
mod_pow:

signed main(){
  int n,m;
  cin>>m>>n;
  cout<<mod_pow(m,n,MOD)<<endl;
}

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_B&lang=jp

euler_phi:

signed main(){
  int n;
  cin>>n;
  cout<<euler_phi(n)<<endl;
  return 0;
}

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_D&lang=jp

extgcd:


http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_E&lang=jp

*/

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

int a,b;
int map[20][20];
int n;

void sim(void){

  for(int i = 0; i < a; i++){
    for(int j = 0; j < b; j++){

      if(map[i][j] != -1){ 
	
	
	if(i == 0 && j == 0) map[i][j] = 1;
	else if(i == 0){
	    map[i][j] = map[i][j-1];
	}else if(j == 0){
	  map[i][j] = map[i-1][j];
	}else{
	  if(map[i-1][j] == -1 && map[i][j-1] == -1)
	    map[i][j] = -1;
	  else if(map[i-1][j] == -1)
	    map[i][j] = map[i][j-1];
	  else if(map[i][j-1] == -1)
	    map[i][j] = map[i-1][j];
	  else
	    map[i][j] = map[i-1][j] + map[i][j-1];
	}

      }		  
    }
  }
}


int main(){


  while(1){
    cin >> a >> b;
    if(a == 0 && b == 0) break;
    cin >> n;

    //テ・ツ按敕ヲツ慊淌・ツ個?
    for(int i = 0 ; i < 20 ; i++){
      for(int j = 0; j < 20 ; j++){
	map[i][j] = 0;
      }
    }

    //テ・ツ?・テ・ツ環?
    for(int i = 0; i < n ; i++){
      int x,y;
      cin >> x >> y;
      map[x-1][y-1] = -1;
    }
    sim();
    cout << map[a-1][b-1] << endl;
  }

  return 0;

}

Measured memory_bytes: 1160
D = [[[-1, -1], [0, -1], [1, -1], [1, 0], [0, 1], [-1, 0]],
     [[-1,  0], [0, -1], [1,  0], [1, 1], [0, 1], [-1, 1]]]

w, h = gets.split.map(&:to_i)
w += 2; h += 2
fld = h.times.map{ [false]*w }
(h-2).times{ |i| gets.split(" ").each_with_index{ |e, j| fld[i+1][j+1] = true if e == "1" } }

tmp = h.times.map{ [false]*w }
arr = []
arr << [0, 0]
tmp[0][0] = true
until arr.empty?
  y, x = arr.shift
  D[y%2].each do |dy, dx|
    u = y + dy; v = x + dx
    next if u < 0 || u >= h || v < 0 || v >= w
    if !fld[u][v] && !tmp[u][v]
      tmp[u][v] = true
      arr << [u, v]
    end
  end
end
fld = fld.flatten.zip(tmp.flatten).map{ |f, t| !(!f & t) }
p fld.map.with_index{ |e, i| D[(i/w)%2].count{ |y, x| !fld[i+y*w+x] } if e }.compact.reduce(:+)

Measured memory_bytes: 9484
import itertools
n = int(input())
v = list(map(int, input().split()))
c = list(map(int, input().split()))
xy = 0
for i in range(1,n+1):
    for h in itertools.combinations(range(0,n),i):
        x = 0
        y = 0
        for j in h:
            x += v[j]
            y += c[j]
        if xy < x-y:
            xy = x-y
print(xy)

Measured memory_bytes: 9136
///
// File:  b.go
// Author: ymiyamoto
//
// Created on Sun Jun  3 23:44:53 2018
//
package main

import "fmt"

var A string

func main() {
	fmt.Scan(&A)
	m := map[uint8]int64{}
	for i := range A {
		m[A[i]]++
	}

	num := int64(len(A)) * int64(len(A)-1) / 2
	for _, v := range m {
		num -= v * (v - 1) / 2
	}

	fmt.Println(num + 1)
}


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

int main(){
  int N,T; cin >> N >> T;
  vector<pair<int,int>> MY(N);
  for(int i=0;i<N;i++){
    cin >> MY.at(i).first >> MY.at(i).second;
  }
  sort(MY.begin(), MY.end());
  int count=0;
  for(int i=0;i<N;i++){
    if(MY.at(i).second<=T){
      cout << MY.at(i).first << endl;
      break;
    }
    count++;
  }
  if(count==N){
    cout << "TLE" << endl;
  }
}

Measured memory_bytes: 256
//  s.at(0) = toupper(s.at(0));//小文字なら大文字へ//大文字の場合はそのまま
//  s.at(i) = tolower(s.at(i));//大文字なら小文字へ//小文字の場合はそのまま
//s配列に格納した単語を、辞書順にソートする
//getline(cin, s);
//  sort(s.begin(), s.end());
//  string t = "keyence";//で文字列入力ができる
//s.empty() //emptyなら1を出力 入っていれば0を出力
/*//ABC018-B 部分的にreverseをかける解法
int main() {
  string s;
  cin >> s;
  int n;
  cin >> n;
  vector<int>a(n);
  vector<int>b(n);
  rep(i,n) cin>>a.at(i)>>b.at(i);
  rep(i,n)a.at(i)--;
  rep(i,n)b.at(i)--;
  string t;
  rep(i,n){
    t = s;
    for(int k=0;k<=b.at(i)-a.at(i);k++){
      t.at(a.at(i)+k) = s.at(b.at(i)-k);
    }
    s = t;
  }
  cout << s << endl;
}
*///ABC018-B
//  string s;
//  cin >> s;
//  cout << s.at(0) <<endl;
//  cout << s.at(0)-'0' <<endl;
//  Aが16？
//  cout << char(i+48) << endl;//なぜかaは47と得る時がある。+48で出力もaにできる。
//  cout << char(97) << endl;//アスキーコードでaを出力
// sort(b.begin(), b.end());//bという配列を小さい方からソート
// reverse(b.begin(), b.end());//bという配列をリターン
// 10桁でdouble出力するパターン１ 
// printf("%.10f\n", ma);
// 10桁でdouble出力するパターン２
//cout << fixed << setprecision(10);
//  cout << ma << endl;

/*01 02 03 12 13 23　と６回見ていくパターン 
for(int i=0;i<n-1;i++){
  for(int j=i+1;j<n;j++){
    }
  }
*///vector<vector<int>> data(3, vector<int>(4));//int型の2次元配列(3×4要素の)の宣言
//int64_t a;
//10のi乗pow(10, i);
/*string s; stringでの文字列を数字型に変える方法
  cin >> s;
  rep(i,s.size()-2) {
  int a= (s.at(i)-'0')*100 + (s.at(i+1)-'0')*10+ s.at(i+2) -'0';
    */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int gcd(ll a, ll b)
{
   if (a%b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a%b));
   }
}

ll lcm(ll a, ll b)
{
   return a * b / gcd(a, b);
}
int kan_hyaku(int n){
  int kurai = 0;
  for(int i=0;i<3;i++){
    kurai = n%10;
    n /=10;
  }
  return kurai;
}
int kan_ju(int n){
  int kurai = 0;
  for(int i=0;i<2;i++){
    kurai = n%10;
    n /=10;
  }
  return kurai;
}
int kan_ichi(int n){
  int kurai = 0;
  for(int i=0;i<1;i++){
    kurai = n%10;
    n /=10;
  }
  return kurai;
}
int main() {
  int n;
  cin >> n;
  vector<ll>a(n);
  vector<ll>b(n);
  rep(i,n) cin>> a.at(i) >> b.at(i);
  ll sum = 0;
  for(int i=n-1;i>=0;i--){
//    if( a.at(i) + sum < b.at(i) ){
//      sum += b.at(i) - (sum + a.at(i) );
//    }
//    else{
      ll num = (a.at(i)+sum) % b.at(i);
      if(num != 0){
        sum += b.at(i) - num;
//      }
    }
  }
  cout << sum << endl;
}
/*
  for(int i=n-1;i>=0;i--){
    if( a.at(i) + sum <= b.at(i) ){
      sum += b.at(i) - (sum + a.at(i) );
    }
    else{
      ll num = (a.at(i)+sum) % b.at(i);
      if(num != 0){
        sum += b.at(i) - num;
      }
    }
  }
  cout << sum << endl;
}
*/

/*
  for(int i=n-1;i>=0;i--){
    ll num = b.at(i) - (a.at(i) + sum ) % b.at(i);
    if(num != b.at(i)){
      sum += num;
    }
  }
  cout << sum << endl;
}
*/



Measured memory_bytes: 4852
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace AtCoder.D
{
    public class Program
    {
        public static void Main() { var r = GetResult(); Debug.WriteLine(r); Console.Write(r); }

        private static object GetResult()
        {
            var N = ReadLong();
            var A = ReadLongs();
            // すべて正とする
            var pA = A.Select(x => x > 0 ? x : -1 * x).ToList();

            // 一つでも0があるとき or 負が偶数の場合 はすべて正にできる
            if (A.Any(x => x == 0) || A.Count(x => x < 0) % 2 == 0)
                return pA.Sum(x => x);

            // 負が奇数の場合 ひとつだけ負の値ができてしまう
            return pA.Sum(x => x) - 2 * pA.Min(x => x);
        }

        #region Console.Read

        public static string ReadText() { return Console.ReadLine(); }
        public static List<string> ReadTexts() { return Console.ReadLine().Split(' ').ToList(); }
        public static long ReadLong() { return long.Parse(Console.ReadLine()); }
        public static (long, long) Read2Longs() { var ls = ReadLongs(); return (ls[0], ls[1]); }
        public static (long, long, long) Read3Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2]); }
        public static (long, long, long, long) Read4Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2], ls[3]); }
        public static (long, long, long, long, long) Read5Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2], ls[3], ls[4]); }
        public static List<long> ReadLongs() { return Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToList(); }

        #endregion
    }
}


Measured memory_bytes: 39700
#include <iostream>
#include <algorithm>
#include <stack>
#include <string>
#include <map>
#include<vector>
#include <cassert>
using namespace std;
template <typename T, const T id>
class CHT {
	struct line {
		T a, b;
		line(T a_ = 0, T b_ = 0) : a(a_), b(b_) {}
		T get(T x) { return a * x + b; }
	};
	struct node {
		line l;
		node *lch, *rch;
		node(line l_) : l(l_), lch(nullptr), rch(nullptr) {}
		~node() {
			if (lch) delete lch;
			if (rch) delete rch;
		}
	};

private:
	const int n;
	const vector<T> pos;
	node *root;

public:
	CHT(const vector<T>& pos_) : n(pos_.size()), pos(pos_), root(nullptr) {}
	~CHT() {
		if (root) delete root;
	}
	void insert(T a, T b) {
		line l(a, b);
		root = modify(root, 0, n, l);
	}
	T get(T x) const {
		int t = lower_bound(pos.begin(), pos.end(), x) - pos.begin();
		assert(t < n && pos[t] == x);
		return sub(root, 0, n, t);
	}

private:
	node * modify(node *p, int lb, int ub, line& l) {
		if (!p) return new node(l);
		if (p->l.get(pos[lb]) >= l.get(pos[lb]) && p->l.get(pos[ub - 1]) >= l.get(pos[ub - 1])) return p;
		if (p->l.get(pos[lb]) <= l.get(pos[lb]) && p->l.get(pos[ub - 1]) <= l.get(pos[ub - 1])) {
			p->l = l;
			return p;
		}
		int c = (lb + ub) / 2;
		if (p->l.get(pos[c]) < l.get(pos[c])) swap(p->l, l);
		if (p->l.get(pos[lb]) <= l.get(pos[lb]))
			p->lch = modify(p->lch, lb, c, l);
		else
			p->rch = modify(p->rch, c, ub, l);
		return p;
	}
	T sub(node *p, int lb, int ub, int t) const {
		if (!p) return id;
		if (ub - lb == 1) return p->l.get(pos[t]);
		int c = (lb + ub) / 2;
		if (t < c) return max(p->l.get(pos[t]), sub(p->lch, lb, c, t));
		return max(p->l.get(pos[t]), sub(p->rch, c, ub, t));
	}
};
int tizu[704] = { 0 };
int graph[703][703] = { 0 };
int judge = 0;
int n, m;
int num[3] = { 0 };
void dfs(int now) {
	for (int i = 1; i <= n; i++) {
		if (i == now)continue;
		if (graph[now][i] == 0) {
			if (tizu[i] == tizu[now]) {
				judge = 1; return;
			}
			if (tizu[i] == 0) {
				if (tizu[now] == 1)tizu[i] = 2;
				else tizu[i] = 1;
				num[tizu[i]] += 1;
				dfs(i);
			}
		}
	}
}
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n >> m;
	int a, b;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		graph[a][b] = 1;
		graph[b][a] = 1;
	}
	vector<int>vec;
	for (int i = 1; i <= n; i++) {
		if (tizu[i] == 0) {
			tizu[i] = 1;
			num[1] += 1;
			dfs(i);
			if (judge == 1)break;
			vec.push_back(abs(num[1] - num[2]));
			num[1] = 0;
			num[2] = 0;
		}
	}
	if (judge == 1) { cout << -1; return 0; }
	int dp[704][704];
	dp[0][0] = 1;
	for (int i = 0; i < vec.size(); i++) {
		for (int j = 0; j <= 702; j++) {
			if (dp[i][j] == 1) {
				dp[i+1][abs(j + vec[i])] = 1;
				dp[i+1][abs(j - vec[i])] = 1;
			}
		}
	}
	for (int i = 0; i <= n; i++) {
		if (dp[vec.size()][i] == 1) {
			int num1 = (n + i) / 2;
			int num2 = (n - i) / 2;
			cout << num1 * (num1 - 1) / 2 + num2 * (num2 - 1) / 2;
			break;
		}
	}
	return 0;
}


Measured memory_bytes: 4096
#include <iostream>
#include <vector>
#include <queue>

using namespace std;
using ll = long long;

int main(){
    int N,A,sumA;
    cin >> N >>A;
    vector<int> x(N+1);
    int m = A;
    for(int i=1;i<=N;i++){
        cin >> x[i];
        m = max(m, x[i]);
    }
    vector<vector<vector<ll> > > dp(N+1, vector<vector<ll> >(N+1, vector<ll>(N*m+1,0)));
    dp[0][0][0] = 1ll;

    for(int i=0;i<=N;i++){
        for(int k=0;k<=i;k++){
            for(int t=0;t<=N*m;t++){
                if(i >= 1 && k >= 1 && t - x[i] >= 0){
                    dp[i][k][t] = dp[i-1][k][t] + dp[i-1][k-1][t-x[i]];
                }else if( i >= 1 && t - x[i] < 0){
                    dp[i][k][t] = dp[i-1][k][t];
                }
            }
        }
    }
    ll ans = 0ll;
    for(int k=1;k<=N;k++){
        ans += dp[N][k][k*A];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 52224
#include<bits/stdc++.h>
using namespace std;
#define int  long long 
#define speedrap ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int be(int a,int b,int mod) {if(b == 0) return 1; if(b%2 == 1) return (a*be(a,b-1,mod))%mod; else return (be(a,b/2,mod)*be(a,b/2,mod))%mod;}
const int mod = 1e9 + 7;
#define PI 3.14159265359
#define pf push_front
#define pb push_back
#define bitcount __builtin_popcountll
#define setbitcnt __builtin_ctz
#define sc(a) scanf("%d", &a);
#define sz(s) (int)s.size()
#define eb emplace_back
#define pf push_front
#define mkp(x,y) make_pair(x,y)
#define all(x) x.begin(),x.end()
#define INF 0x3f3f3f3f
#define roundup(a,b)  std::cout << std::fixed;std::cout << std::setprecision(b); std::cout << a
const int siz = (1e5 + 10);
const int logi = 21;
const double epsilon = 1e-6;
bool cmp(const int &a,const int &b)
{
  return (abs(a-b)>1);
}


signed main()
{
	#ifndef ONLINE_JUDGE
 	freopen("in.txt", "r", stdin);
 	freopen("out.txt", "w", stdout);
 	#else
// // online submission
 	#endif 
	speedrap
	int t;
	t = 1;
	//cin>>t;
	while(t--)
	{
		
		double a,b;
		double h,m;
		cin>>a>>b>>h>>m;

		double angle1 = (2*PI*(h + m/60))/12.00;
		double angle2 = (2*PI*m)/60.00;

		double diff = abs(angle1-angle2);
		diff = min(diff,2*PI - diff);


		//cout<<diff<<"\n";

		double c = a*a + b*b - 2*a*b*cos(diff);
		c = sqrt(c);
		roundup(c,9);
	}
}

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

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

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

  vector<ll> count(5,0); //MARCH
  rep(i,n){
    string s;
    cin >> s;
    if(s.at(0)=='M') count.at(0)++;
    else if(s.at(0)=='A') count.at(1)++;
    else if(s.at(0)=='R') count.at(2)++;
    else if(s.at(0)=='C') count.at(3)++;
    else if(s.at(0)=='H') count.at(4)++;
  }

  ll ans=0;
  for(int i=0; i<3; i++){
    for(int j=i+1; j<4; j++){
      for(int k=j+1; k<5; k++){
        ll p = count.at(i)*count.at(j)*count.at(k);
        ans += p;
      }
    }
  }

  cout << ans;
}

Measured memory_bytes: 3588
def main():
    a, b, c, d = map(int, input().split())
    kai_a = a // d
    kai_c = c // b
    amari_a = a % d
    amari_c = c % b
    
    if kai_a > kai_c:
        print('Yes')
    elif kai_a == kai_c:
        if amari_c == 0:
            print('Yes')
        elif amari_a == 0:
            print('No')
        else:
            print('Yes')
    else:
        if amari_c == 0 and amari_a > 0:
            print('Yes')
        else:
            print("No")

 
if __name__ == '__main__':
    main()

Measured memory_bytes: 9200
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  char x , y;  cin >> x >> y;
  int xxx,yyy;
  if(x=='A') xxx=10;
  if(y=='A') yyy=10;
  if(x=='B') xxx=11;
  if(y=='B') yyy=11;
  if(x=='C') xxx=12;
  if(y=='C') yyy=12;
  if(x=='D') xxx=13;
  if(y=='D') yyy=13;
  if(x=='E') xxx=14;
  if(y=='E') yyy=14;
  if(x=='F') xxx=15;
  if(y=='F') yyy=15;
  
  if(xxx==yyy) cout <<"="<<endl;
  if(xxx>yyy) cout<<">"<<endl;
  if(xxx<yyy) cout<<"<"<<endl;
    
    
    
    
    
    
    
    
    
    
    
    
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        
        Scanner sc = new Scanner(System.in);
        
        long A = sc.nextLong();
        long B = sc.nextLong();
        long C = sc.nextLong();
        long D = sc.nextLong();
        
        System.out.println( f(B, C, D) - f(A - 1, C, D) );
        
    }
    
    // x以下でcまたはdで割り切れない数の個数
    public static long f(long x, long c, long d){
        return x - x / c - x / d + x / LCM(c, d);
    }
    
    public static long GCD(long a, long b){
        if ( b == 0 ) return a; 
        return GCD(b, a % b);
    }
    
    public static long LCM(long a, long b){
        return a * b / GCD(a, b);
    }
}


Measured memory_bytes: 21844
#include <iostream>
using namespace std;
int main(){
	int N, M, X, A[100], i;
	cin >> N >> M >> X;
	for (i = 0; i < M; i++){
		cin >> A[i];
		if (X < A[i])
			break;
	}
	cout << ((i < M - i) ? i : M - i) << endl;


}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	char n[4];
	scanf("%s",&n);
	if(n[1]==n[2] && (n[0]==n[1] || n[2]==n[3])){
		printf("Yes\n");
	}
	else{
		printf("No\n");
	}
	return 0;
}

Measured memory_bytes: 128
#include<iostream> 
using namespace std;
int main()
{
	int a,b,T;
	cin>>a>>b>>T;
	int f=0; 
	while(T--){
		if(f==0){
			if(a%2!=0){
				a--;
			}
			b+=a/2;
			a/=2;
			f=1;
		}
		else{
			if(b%2!=0){
			b--;
			}
			a+=b/2;
			b/=2;
			f=0;
		}		
	}
	cout<<a<<" "<<b<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  string A,B,C;
  cin>>A>>B>>C;
  if(A[A.size()-1]==B[0]&&B[B.size()-1]==C[0]) cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
  return 0;
}

Measured memory_bytes: 256
#include<cmath>
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
stack<int> st;
queue<int> qu;
queue<pair<int,int> > qu2;
priority_queue<int> pq;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define rep2(i,n) for(int i=1; i<=(int)(n); i++)
#define mins(x,y) x=min(x,y)
#define maxs(x,y) x=max(x,y)
#define ALL(a) a.begin(), a.end()
typedef set<int> set_t;
typedef set<string> set_g;
typedef complex<double> xy_t;
static const int NIL = -1;
static const int INF = 1000000007;
#define mp make_pair
#define sz(x) int(x.sise())
#define mod 1000000007
#define reps(i,s,n) for(int i = s; i < n; i++)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
deque<int> deq;
#define fi first
#define se second
//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
typedef pair<int, int> P;
typedef vector<ll> vec;
typedef vector<vec> mat;
int main(){
    int d,t,s;
    cin >> d >> t>> s;
    if(s*t>=d){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    return 0;
}

Measured memory_bytes: 3628
#include <cstdio>
#include <algorithm>


using namespace std;


const int SIZE = 50+10;
int A[SIZE];

int main (void)
{
	int N,K;
	scanf("%d %d",&N,&K);
	for(int i=0;i<N;i++)
		scanf("%d",A+i);
	sort(A,A+N);
	int sum = 0;
	for(int i=N-1;K-->0;i--)
		sum += A[i];
	printf("%d\n",sum);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define ALL(a)  (a).begin(),(a).end()
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
template <typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
const int INT_INF = 1LL << 30;

int N;
vll m(110), n(110);
vvll dp(110, vll(110, INF));

ll res(int l, int r){ //[l, r)での最小回数
  if(dp.at(l).at(r) != INF) return dp.at(l).at(r);
  if(r-l == 1) return dp.at(l).at(r) = 0;
  if(r-l == 2) return dp.at(l).at(r) = m.at(l) * n.at(l) * n.at(r-1);

  ll result = INF;
  for(int i = l+1; i <= r-1; i++){ //[l, i), [i, r)に分割
    chmin(result, res(l, i) + res(i, r) + m.at(l) * m.at(i) * n.at(r-1));
  }
  return dp.at(l).at(r) = result;
}

int main(){
  cin >> N;
  for(int i = 0; i < N; i++){
    cin >> m.at(i) >> n.at(i);
  }

  cout << res(0, N) << endl;
}


Measured memory_bytes: 3260
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

struct S {
  int p[8][8];
  S() { fill_n((int*)p, 8 * 8, -1); }
  // bool operator < (const S &s) const {
  //   for (int i = 0; i < 8; i++) {
  //     for (int j = 0; j < 8; j++) {
  //       if (p[i][j] != s.p[i][j]) return p[i][j] < s.p[i][j];
  //     }
  //   }
  // }
};

int dy[4] = {0, -1, 0, 1};
int dx[4] = {1, 0, -1, 0};
int h, w, c;
int used[8][8];

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

int dfs(S *s, int y, int x, int c, int flag) {
  int res = 1;
  char ch = flag ? c : s->p[y][x];
  used[y][x]++;
  for (int i = 0; i < 4; i++) {
    int ny = y + dy[i];
    int nx = x + dx[i];
    if (contain(ny, nx) && !used[ny][nx] && s->p[ny][nx] == ch) {
      res += dfs(s, ny, nx, c, flag);
    }
  }
  s->p[y][x] = c;
  return res;
}

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  while (cin >> h >> w >> c, h) {
    S s;
    for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++) {
        cin >> s.p[i][j];
      }
    }
    using P = pair<int, S>;
    queue<P> que;
    que.emplace(0, s);
    int ans = 0;
    while (!que.empty()) {
      P p = que.front(); que.pop();
      S curr = p.second;
      if (p.first == 5) continue;
      for (int i = 1; i <= 6; i++) {
        if (curr.p[0][0] == i) continue;
        S next = curr;
        fill_n((int*)used, 8 * 8, 0);
        dfs(&next, 0, 0, i, 0);
        fill_n((int*)used, 8 * 8, 0);
        if (i == c && p.first + 1 == 5) {
          ans = max(ans, dfs(&next, 0, 0, i, 1));
        }
        que.emplace(p.first + 1, next);
      }
    }
    cout << ans << endl;
  }  

  return 0;
}


Measured memory_bytes: 3664
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <climits>
using namespace std;
#define ll long long

int d = 365;
//int k = 0;
vector<vector<int>> s(d, vector<int>(26, 0));
vector<ll> c(26);

void init() {
    cin >> d;
    for(int i = 0; i < 26; i++) cin >> c[i];
    for(int i = 0; i < d; i++) {
        for(int j = 0; j < 26; j++) {
            cin >> s[i][j];
        }
    }
    return;
}

ll calc(vector<int> out) {
    ll score = 0;
    vector<ll> last(26, 0);
    for(int i = 0; i < out.size(); i++) {
        //cout << i << endl;
        last[out[i]] = i+1; // タイプ番号
        //cout << "out[" << i << "] " << out[i] << " ";
        for(int j = 0; j < 26; j++) {
            score -= c[j]*((i+1)-last[j]);
        }
        score += s[i][out[i]];
        //cout << "score : " << score << endl;
    }

    //int p = min(int(out.size()+k), int(d));
    //cout << p << endl;
    //if(out.size() >= d) return score;
    //cout << k << endl;
    //cout << out.size() << " " << d << endl;
    //int p = min(int(out.size()+k), d);
    ll q = 0;
    ll score_tmp = LLONG_MIN;
    for(int k = 0; k < 26; k++) {
        q = 0;
        int p = min(int(out.size()+k), d);
        for(int i = out.size(); i < p; i++) {
            //cout << i << endl;
            for(int j = 0; j < 26; j++) {
                q -= c[j]*((i)-last[j]);
            }
            //cout << score << endl;
        }
        if(score-score_tmp < score-q) {
            score_tmp = q;
        }
    }
    return score-q;
}

/*
vector<int> proc(int k) {
    vector<int> out;
    ll ans = 0;
    //ll tmp = 0;
    ll max_v = -1;
    //for(int k = 0; k < 26; k++) {
    //cout << "k: " << k << endl;
    //vector<int> out;
    for(int i = 0; i < d; i++) {
        //max_v = -100000000000;
        max_v = LLONG_MIN;
        int best = 0;
        for(int j = 0; j < 26; j++) {
            out.push_back(j);
            ll tmp = calc(out);
            if(max_v < tmp) {
                max_v = tmp;
                best = j;
            }
            out.pop_back();
        }
        out.push_back(best);
    }
    //}
    return out;
}
*/

int main() {
    init();
    /*
    vector<int> out;
    vector<int> ans;
    for(int i = 0; i <= 26; i++) {
        out = proc(i);
        for(int j = 0; j < out.size(); j++) {

        }
    }
    */
    
    vector<int> out;
    ll ans = 0;
    ll max_v = -1;
    //for(int k = 0; k < 26; k++) {
        //cout << "k: " << k << endl;
        //vector<int> out;
    for(int i = 0; i < d; i++) {
        //max_v = -100000000000;
        max_v = LLONG_MIN;
        int best = 0;
        for(int j = 0; j < 26; j++) {
            out.push_back(j);
            //for(int k = 0; k < 26; k++) {
            ll tmp = calc(out);
            if(max_v < tmp) {
                max_v = tmp;
                best = j;
            }
            //}
            out.pop_back();
        }
        out.push_back(best);
    }
    //}
    
    for(int i = 0; i < d; i++) {
        cout << out[i]+1 << endl;
    }
    //cout << max_v << endl;
    return 0;
}

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

int a[10000];
int b[10000];

int main() {
  int n;
  long long dif = 0, op = 0;
  bool ok = true;
  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]);
    if(a[i] < b[i])
      dif = dif + (b[i] - a[i] + 1) / 2;
    op = op + b[i] - a[i];
  }

  if(dif <= op)
    printf("Yes");
  else
    printf("No");
  return 0;
}


Measured memory_bytes: 384
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import copy

N, K = list(map(int, sys.stdin.readline().rstrip().split()))
data = []
for _ in range(N):
    A, B = list(map(int, sys.stdin.readline().rstrip().split()))
    data.append([A, B])

ans = 0


def lower(x, y):
    if(x > y):
        return False
    # print(bin(x), bin(y), bin(x|y), bin((x | y) ^ y))
    if((x | y) ^ y) == 0:
        return True
    else:
        return False


Nstr = list(reversed(bin(K)[2:]))
subNs = [K]
for i in range(len(Nstr)):
    if Nstr[i] == "0":
        continue
    subNstr = copy.deepcopy(Nstr)
    subNstr[i] = "0"
    for j in range(i):
        subNstr[j] = "1"

    realstr = ""
    for s in reversed(subNstr):
        realstr += s
    subNs.append(int(realstr, 2))


for subNstr in subNs:
    subans = 0
    for A, B in data:
        # print(A, subNstr, lower(A, subNstr))
        if(lower(A, subNstr)):
            subans += B
    # print(subNstr, subans)
    ans = max(subans, ans)

print(ans)

exit(0)


Measured memory_bytes: 57180
#include"bits/stdc++.h"
using namespace std;

int main() {
	int N;
	cin >> N;
	int ans = N % 10;
	if (ans == 2 || ans == 4 || ans == 5 || ans == 7 || ans == 9) {
		cout << "hon" << endl;
	}
	else if (ans == 0 || ans == 1 || ans == 6 || ans == 8){
		cout << "pon" << endl;
	}
	else if (ans = 3) {
		cout << "bon" << endl;
	}
}

Measured memory_bytes: 3648
#include <stack>
#include <stdio.h>
#include <vector>

using namespace std;

#define NMAX 100000
#define NIL -1

int n;
stack<int> S;
vector<int> adj[NMAX + 1]; // 0-origin
int d[NMAX + 1];           // if visited
int c[NMAX + 1];           // color

int next_unvisited() {
    for (int i = 0; i < n; i++) {
        if (d[i] == 0)
            return i;
    }
    return NIL;
}

int next_unvisited_adj(int u) {
    vector<int>::iterator it;
    for (it = adj[u].begin(); it != adj[u].end(); it++) {
        if (d[*it] == 0)
            return *it;
    }
    return NIL;
}

void dfs() {
    int x; // start vertex;
    int round = 0;
    while ((x = next_unvisited()) != NIL) {
        d[x] = 1;
        c[x] = round;
        S.push(x);
        while (!S.empty()) {
            int u = S.top();
            int v = next_unvisited_adj(u);
            if (v != NIL) {
                if (d[v] == 0) {
                    d[v] = 1;
                    c[v] = round;
                    S.push(v);
                }
            } else {
                S.pop();
            }
        }
        round++;
    }
}

int main() {
    int m, q, u, v;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 0; i < n; i++)
        d[i] = 0;
    dfs();
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        scanf("%d %d", &u, &v);
        if (c[u] == c[v])
            printf("yes\n");
        else
            printf("no\n");
    }
    return 0;
}


Measured memory_bytes: 9164
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using ld = long double;
const int maxn = 1<<18;
struct ci {
	int x = 0, y = 0, r = 0, vis = 0;
	ld dist = 1ll<<61;
};

ci c[maxn];
int n, vis[maxn];
ld dist(int i, int j) {
	return max((ld)0, sqrt((c[i].x-c[j].x)*(ld)1*(c[i].x-c[j].x) + (c[i].y-c[j].y)*(ld)1*(c[i].y-c[j].y)) - c[i].r - c[j].r);
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	for(int i = 0; i < 2; i++)
		cin >> c[i].x >> c[i].y;
	cin >> n;
	for(int i = 2; i <= n+1; i++)
		cin >> c[i].x >> c[i].y >> c[i].r;
	c[0].dist = 0;
	for(int iter = n+1; iter--;) {
		int p = -1;
		for(int i = 0; i <= n+1; i++) if(!c[i].vis && (p == -1 || c[i].dist < c[p].dist)) p = i;
		c[p].vis = 1;
		for(int i = 0; i <= n+1; i++) c[i].dist = min(c[i].dist, c[p].dist + dist(p, i));
	}
	cout << fixed << setprecision(15) << c[1].dist;
}


Measured memory_bytes: 256