akhauriyash/Code-Regression huggingface dataset:
s_str, u_str = gets.split(" ").map{|str| str.chomp}

s_count, u_count = gets.split(" ").map{|i| i.to_i}

reject_str = gets.chomp

if s_str == reject_str
  s_count -= 1
elsif u_str == reject_str
  u_count -= 1
end

puts "#{s_count} #{u_count}"


Measured memory_bytes: 1788
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

class Main{

	static int N;
	static int M;
	static 		ArrayList<ArrayList<Integer>> map;



	public static void main(String[] args) {


		Scanner sc = new Scanner(System.in);			//文字の入力
		N = sc.nextInt();
		M = sc.nextInt();
		int[] l = new int[N];
		for(int i = 0;i < N;i++){
			l[i] = sc.nextInt();
		}
		Arrays.sort(l);
		int ans = 0;
		for(int i = N-1;i >N-M-1;i--){
			ans += l[i];
		}
		
		System.out.println(ans);

	}

}




Measured memory_bytes: 21588
#include<stdio.h>
#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<utility>
#include<stack>
#include<algorithm>
#include<string>
#include<string.h>
#include<assert.h>
#include<iomanip>
#include<unordered_map>
#define F first
#define S second
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;

int main(){
  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  int n, a, b; cin >> n >> a >> b;
  int tmp = b / n - (a - 1) / n;
  if(tmp > 0)cout << "OK" << endl;
  else cout << "NG" << endl;
}


Measured memory_bytes: 3652
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
typedef long long ll;
#define rep(i, a, n) for (int i = (a); i < (n); i++)
#define repr(i, n, a) for (int i = (n)-1; i >= (a); i--)
#define each(it, v) for (auto(it) = (v).begin(); (it) != (v).end(); (it)++)
#define all(v) (v).begin(), (v).end()
#define vi vector<int>
#define vvi vector<vi>
#define vd vector<double>
#define vvd vector<vd>
#define co(x) cout << (x)
#define con(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
const int N = 2e5 + 9, INF = 0x3f3f3f3f;
/******* V ************************************/
int n, k, w[N];
/******* F ************************************/
int check(int p)
{
  int cnt = 0, i = 0, sum = 0;
  while (i < n)
  {
    if (sum + w[i] <= p)
    {
      sum += w[i];
      i++;
    }
    else
    {
      cnt++;
      sum = 0;
    }
    if (cnt >= k) break;
  }
  if (sum) cnt++;
  return cnt <= k && i == n;
}
/******* M ****************************************/
void Main()
{
  cin >> n >> k;
  rep(i, 0, n) cin >> w[i];
  int l = 0, r = INF, mid;
  while (l < r)
  {
    mid = (l + r) / 2;  // l+r>>1;
    if (check(mid))
      r = mid;
    else
      l = mid + 1;
  }
  cout << r << endl;
}
/******************************************************
  Smaile!
▕▔╲┊┊┊┊┊┊┊┊┊╱▔▏
┊╲┈╲╱▔▔▔▔▔╲╱┈╱┊
┊┊╲┈╭╮┈┈┈╭╮┈╱┊┊
┊┊╱┈╰╯┈▂┈╰╯┈╲┊┊
┊┊▏╭╮▕━┻━▏╭╮▕┊┊
┊┊╲╰╯┈╲▂╱┈╰╯╱
                    How`s it going?
                            |＼
                    　／￣＼　ヽ
                    ／　　　ヽ |_
                    ￣＼　　　　 ＼
                    ／￣　/|/| /ﾚ､ ヽ＿
                    ￣＼ Yヘ |/ヘ幺　∠
                    　＜_|(･> <･) 6) ／
                      　　 (ﾞ　_　ﾞ／＜
                      　　　＞､ーイ￣￣
                    　　／厂ヽ／￣/＼
                    　 ( ｜　(亀)(>　)▏

                            Take a rest before getting tired!
                                        　　 ●
                                        　　/⌒ヽ
                                        　 ｜ 　|/⌒ヽ(ヽ
                                        　 (｀　∥ー⌒) |
                                        　|￣||￣￣￣￣￣|
                                        　|―||―――――|
                                        　|　Ｕ　　　　　|
                                        　|￣￣￣￣￣￣￣|
                                        　|＿＿＿＿＿＿＿|
                                        　　|―――――|
                                        　　|―――――|
                                        ｗｗＷｗｗＷｗＷＷｗ

******************************************************/
int main()
{
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  Main();
  return 0;
}


Measured memory_bytes: 3596
///Bismillahir Rahmanir Rahim
#include<bits/stdc++.h>

#define                           int                         long long
#define                           fi                          first
#define                           si                          second
#define                           mp                          make_pair
#define                           pb                          push_back
#define                           pi                          pair<int,int>
#define                           f(i,l,r)                    for(int i=l;i<=r;i++)
#define                           rf(i,r,l)                   for(int i=r;i>=l;i--)
#define                           done(i)                     cout<<"done = "<<i<<endl;
#define                           fast                        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);




using namespace std;

const int inf=1e18;
const int mod=1e9+7;
const int M=100009;
inline int bigmod(int B,int P){int R=1;while(P>0){if(P&1){R=(R*B)%mod;}P>>=1;B=(B*B)%mod;}return R;}


 main()

{
    fast
    int n,k;
    cin>>n>>k;
    vector<int>vec;
    f(i,1,n)
    {
        int x;
        cin>>x;
        vec.pb(x);
    }
    int sum=0;
    sort(vec.rbegin(),vec.rend());
    f(i,0,n-1)
    {
        if(k>=1)
        {
            k--;
        }
        else
        {
            sum+=vec[i];
        }
    }
    cout<<sum<<endl;
    return 0;

}













Measured memory_bytes: 2420
#include<iostream>
using namespace std;
#define int long long
const int mod = 1000000007;
int invmodd(int x, int modd = mod, int s0 = 1, int s1 = 0){
    return modd?invmodd(modd,x%modd,s1,s0-s1*(x/modd)):s0;
}
inline int invmod(int x){ return (invmodd(x)%mod+mod)%mod; }
int pA[100001]={1}, pB[100001]={1};
signed main(){
    int a, b, c, n;
    cin >> n >> a >> b >> c;
    int X = invmod(a+b), A = a*X%mod, B = b*X%mod, ans = 0, bin = 1;
    for(int i = 0; i < n; i++)pA[i+1] = pA[i]*A%mod, pB[i+1] = pB[i]*B%mod;
    for(int i = 0; i < n; i++){
        if(i) bin = bin*(i+n-1)%mod*invmod(i)%mod;
        ans = (ans + (pA[i] * pB[n] + pA[n] * pB[i])%mod*bin%mod*(n+i))%mod;
    }
    cout << ans*100%mod*X%mod << endl;
}


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

int main(){
  int n,k;
  cin>>n>>k;
  vector<int> a(n);
  rep(i,n) cin>>a[i];
  
  vector<int> b(n);
  
  rep(i,k){  
    rep(j,n){      
      b[max(0,j-a[j])]++;
      if(j+a[j]+1<n) b[j+a[j]+1]--;      
    }    
    bool flag=true;
    a[0]=b[0];
    b[0]=0;
    if(a[0]!=n) flag=false;
    rep(i,n-1){
      a[i+1]=b[i+1]+a[i];
      if(a[i+1]!=n) flag=false;
      b[i+1]=0;
    }
    if(flag){
      rep(p,n) cout<<n<<" ";
      return 0;
    }
  }
  rep(i,n) cout<<a[i]<<" ";
}

Measured memory_bytes: 4840
N = int(input())
stones = list(input())
left = -1
right = N
ans = 0
while left < right:
    l = left
    r = right
    for i in range(l+1,N):
        if stones[i] == "W":
            left = i
            break
    else:
        left = N
    for i in reversed(range(right)):
        if stones[i] == "R":
            right = i
            break
    else:
        right = -1
    if left < right:
        ans += 1
print(ans)

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

using namespace std;
#define ll long long int
ll ans = INT_MAX;
int main()
{
   ll t;
   t = 1;	
   //cin t;
   while(t--){
        ll n, m ,x;
        cin >> n >> m >> x;
        ll cost[n];
        ll value[n][m];
        for(int i = 0 ; i< n ; i ++)
        {   cin >> cost[i];
            for(int j =0 ; j < m;  j++)
            {
                cin >> value[i][j];
            }
        } 
        ll present = 0; 
     //   cout << (1 << n) << endl;
        for(int i = 0; i < (1 << n) ; i ++)
        {
            present = 0;
            ll total[m];
            for(int i1 =0 ; i1 < m ;i1  ++)
            total[i1] = 0;
            ll count =0 ;
            for(int j =0 ; j < n ; j ++)
            {
                ll temp = 1 << j;
                if(i & temp)
                {   
                    present += cost[j];
                    for(int k =0 ; k < m;k ++)
                    {
                        total[k] += value[j][k];
                    }
                }
            }
            for(int j = 0; j < m ;j ++)
            {
                
                if(total[j] >= x)
                count ++;
            }
        
            if(count == m)
            {
                ans = min(ans , present);
            }
        }
        if(ans == INT_MAX)
        cout << "-1" << endl;
        else
        cout << ans << endl;
   }
}


Measured memory_bytes: 3520
n = int(input())
h = list(map(int, input().split()))
r = 0
if len(h) == 1:
    print(h[0])
    exit()
while len(list(set(h))) != 1:
    t = 0
    for k in h:
        if k > 0:
            t = 1
        else:
            if t == 1:
                r += 1
            t = -1
    if t == -1:
        r -= 1
    for i, j in enumerate(h):
        if j != 0:
            h[i] -= 1
    r += 1
print(r)


Measured memory_bytes: 3060
import java.util.Scanner;
import java.util.stream.Stream;


public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] S = Stream.of(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
//		String[] S = sc.nextLine().split("");
		
		int P   = S[0];
		int Q   = S[1];
		int R   = S[2];
		int min_value=0;
		
		min_value = P + Q;
		
		if(R + Q < min_value) min_value = R + Q;
		if(P + R < min_value) min_value = P + R;
		if(Q + R < min_value) min_value = Q + R;
		if(R + P < min_value) min_value = R + P;
		if(Q + P < min_value) min_value = Q + P;
		
		System.out.print(min_value);
	}
}


Measured memory_bytes: 27476
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
constexpr int MOD = 1000000007;
constexpr int INF = 2147483647;
int main()
{
    lint H, W;
    cin >> H >> W;
    if(H == 1 || W == 1) {
        cout << 1 << endl;
        return 0;
    }
    if(H%2 == 0 || W%2 == 0) {
        cout << (H*W/2) << endl;
    } else {
        lint a = (W+1) / 2;
        lint b = (W-1) / 2;
        cout << (a*(H/2+1) + b*(H/2)) << endl;
    }
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    
   int r, c;
   int i, t;
   int table[101][101] = {0};
    
   scanf("%d %d\n", &r, &c);
   for(i = 0; i < r; i++){
       for(t = 0; t < c; t++){
            scanf("%d", &table[i][t]);
       }
        
   }
    
    for(i = 0; i < r; i++){
       for(t = 0; t < c; t++){
            table[i][c] += table[i][t];
            table[r][t] += table[i][t];
       }
        
       table[r][c] += table[i][t];
   }
    
    
      for(i = 0; i < r + 1; i++){
       for(t = 0; t < c + 1; t++){
            if(t != 0) printf(" ");
            printf("%d", table[i][t]);
       }
       printf("\n");
   }
    
    return 0;
}

Measured memory_bytes: 652
s = input()
k = int(input())

if k > 100:
    for i in s:
        if i != '1':
            print(i)
            exit()

elif k <= len(s):
    a = set(s[:k])
    if a == {'1'}:
        print(1)
        exit()
    else:
        for i in s:
            if i != '1':
                print(i)
                exit()
else:
    for i in s:
        if i != '1':
            print(i)
            exit()




Measured memory_bytes: 3060
from itertools import permutations
import sys

sys.setrecursionlimit(10 ** 6)
from bisect import *
from collections import *
from heapq import *

def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def SI(): return sys.stdin.readline()[:-1]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
int1 = lambda x: int(x) - 1
def MI1(): return map(int1, sys.stdin.readline().split())
def LI1(): return list(map(int1, sys.stdin.readline().split()))
p2D = lambda x: print(*x, sep="\n")
dij = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def main():
    n,k=MI()
    if k==0:
        print(n*n)
        exit()
    ans=0
    for b in range(k+1,n+1):
        w=b-k
        c=(n+b)//b
        over=b*c-(n+1)
        ans+=w*c-min(w,over)
    print(ans)

main()


Measured memory_bytes: 3316
N, Q = map(int,input().split())
G = [[] for i in range(N+ 1)]
ANS = [0] * (N + 1)
for _ in range(N - 1):
    a , b = map(int,input().split())
    G[a].append(b)
for _ in range(Q):
    p, x =map(int,input().split())
    ANS[p] += x
from collections import deque
que=deque([])
que.append(1)
while que:
    node = que.pop()
    ans = ANS[node]
    for child in G[node]:
        ANS[child] += ans
        que.append(child)
for i in range(1, N + 1):
    print(ANS[i])


Measured memory_bytes: 87244
# input
X = list(map(int, input().split()))

X.sort()

if (X[1] - X[0]) % 2 == 0:
    ans = X[2] - X[1] + (X[1] - X[0]) // 2 
else:
    ans = X[2] - X[1] + 1 + (X[1] - X[0] + 1) //2

print(ans)

Measured memory_bytes: 3060
#include<iostream>
#include<vector>
using namespace std;
int N;
int c[2<<17];
vector<int>G[2<<17];
int cnt[2<<17];
long ans[2<<17];
int dfs(int u,int p)
{
	int ret=1;
	int sto=cnt[c[u]];
	int pre=sto;
	for(int v:G[u])if(v!=p)
	{
		int t=dfs(v,u);
		ret+=t;
		long k=t-(cnt[c[u]]-sto);
		ans[c[u]]-=k*(k+1)/2;
		sto=cnt[c[u]];
	}
	cnt[c[u]]=pre+ret;
	return ret;
}
main()
{
	cin>>N;
	for(int i=0;i<N;i++)
	{
		cin>>c[i];
		c[i]--;
	}
	for(int i=1;i<N;i++)
	{
		int u,v;cin>>u>>v;u--,v--;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(0,-1);
	for(int i=0;i<N;i++)
	{
		ans[i]+=(long)N*(N+1)/2;
		if(i!=c[0])
		{
			long k=N-cnt[i];
			ans[i]-=k*(k+1)/2;
		}
		cout<<ans[i]<<endl;
	}
}


Measured memory_bytes: 34680
#include <bits/stdc++.h>
using namespace std;
map <string,int>fr;
map <string,int>::iterator it;
int n,i,j,maxi;
string s;
int main()
{
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>s;
        fr[s]++;
        if(fr[s]>maxi)
            maxi=fr[s];
    }
    for(it=fr.begin();it!=fr.end();++it)
        if(it->second==maxi)
            cout<<it->first<<'\n';
    return 0;
}


Measured memory_bytes: 25216
#include<cstdio>
#include<algorithm>
#include<cstring>
#define rep(i, s, t) for(i = s; i <= t; ++i)
#define dep(i, s, t) for(i = s; i >= t; --i)

using namespace std;

const int N = 130, M = N*N;
int n, m;
int d[15][15], p[N][N];
int x[M], y[M], v[M], cnt;

int dis(int A, int B) {
	int ret = 101, i, j;
	rep(i, 0, 100)
		rep(j, 0, 100)
			if(p[i][j] >= 0) ret = min(ret, i*A + j*B + p[i][j]);
	return ret;
}

int main() {
	int i, j, k, A, B; bool f = 1;
	scanf("%d%d", &n, &m);
	rep(i, 1, n) rep(j, 1, m) scanf("%d", &d[i][j]);
	rep(A, 0, 100)
		rep(B, 0, 100) {
			p[A][B] = -100;
			rep(i, 1, n)
				rep(j, 1, m) {
					p[A][B] = max(p[A][B], d[i][j] - i*A - j*B);
				}
			if(p[A][B] >= 0) {
				++cnt;
				x[cnt] = A+1; y[cnt] = B+102; v[cnt] = p[A][B];				
			}
		}
		
	rep(i, 1, n) rep(j, 1, m) 
	if(dis(i, j) != d[i][j]) {puts("Impossible"); return 0;}
		
	
	puts("Possible");
	printf("%d %d\n", 202, cnt+200);
	rep(i, 1, cnt) printf("%d %d %d\n", x[i], y[i], v[i]);
	rep(i, 2, 101) printf("%d %d X\n", i-1, i);
	rep(i, 103, 202) printf("%d %d Y\n", i, i-1);
	puts("1 102");
	return 0;
}

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

int n,ans;
string a;

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

	int red=count(a.begin(),a.end(),'R');
	for(int i=0;i<red;i++)
		if(a[i]!='R') ans++;
	cout<<ans;
}

Measured memory_bytes: 3720
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set> 
#include <map>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
#include <iomanip>
#define rep(i,n) for(int i=0; i<(n); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1001001001; // > 10^9
const int MOD = (int)1e9 + 7;
const ll INFLL = 1001001001001001001;  // > 10^18
const ll MODLL = (ll)1e9 + 7;
const double EPS = 1e-9;

int main () {
    
    ll n,a,b; cin >>n>>a>>b;
    vector<ll> v(n); rep(i,n) cin >> v[i];
    sort(v.begin(), v.end(), greater<ll>());

    ll res = 0;
    for (int i = 0; i < a; i++) {
        res += v[i];
    }
    double m = ((double)res)/a;
    cout << setprecision(10) << m << endl;

    const ll MAX_N = 100; 
    vector<vector<ll> > c(MAX_N, vector<ll>(MAX_N, 0));
    for (ll i = 0; i < MAX_N; i++) {
        c[i][0] = 1;
        c[i][1] = i;
    }
    for (ll i = 1; i < MAX_N; i++) {
        for (ll j = 1; j <= i; j++) {
            c[i][j] = c[i-1][j] + c[i-1][j-1];
        }
    }

    int count0 = 0;
    for (int i = 0; i < n; i++) {
        if (v[i] == v[a-1]) {
            count0++;
        } 
    }

    if (v[0] != v[a-1]) {
        int count = 0;
        for (int i = 0; i < a; i++) {
            if (v[i] == v[a-1]) {
                count++;
            } 
        }
        cout << c[count0][count] << endl;
    } else {
        ll ans = 0;
        for (int l = a; l <= b; l++) {
            ans += c[count0][l];
        }
        cout << ans << endl;        
    } 

    return 0;
}



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

template<typename integer>
integer __lcm(integer a, integer b) {
  return (a * b) / __gcd(a, b);
}


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

  vector<int> a(n);
  rep (i, n) cin >> a[i];

  int ai = 0;
  rep (i, n) ai = max(ai, a[i]);

  int ideal = ai / 2;

  int aj;
  if (ai == a[0]) aj = a[1];
  else aj = a[0];

  int current_score = abs(ideal - a[0]);

  rep (i, n) {
    if (ai == a[i]) continue;

    int new_score = abs(ideal - a[i]);
    if (current_score > new_score) {
      current_score = new_score;
      aj = a[i];
    }
  }

  cout << ai << ' ' << aj << endl;

  return 0;
}



Measured memory_bytes: 640
#include<cstdio>
#include<cstring>
#include<queue>
#define inf 0x3f3f3f3f

using namespace std;

const int N = 2010;

struct note
{
	int to , nex , val , flow;
}g[N << 4];

int n , m , st[N] , S , T , vis[N];
long long ans , dist[N];


inline void add(int u , int v , int val , int flow)
{
	static int tot = 1;
	g[++ tot] = (note){v , st[u] , val , flow} , st[u] = tot;
}

inline void add_edge(int u , int v , int flow ,int val){add(u , v , val , flow) , add(v , u , -val , 0);}

queue<int> q;

int spfa()
{
	while(!q.empty()) q.pop();q.push(S);
	memset(vis , 0 , sizeof vis) , vis[S] = 1;
	memset(dist , -0x3f , sizeof dist) , dist[S] = 0;

	while(!q.empty())
	{
		int u = q.front();q.pop() , vis[u] = 0;
		for(int i = st[u] ; i ;i = g[i].nex)
		{
			int v = g[i].to;
			if(g[i].flow && dist[v] < dist[u] + g[i].val)
				dist[v] = dist[u] + g[i].val , (!vis[v]) && (q.push(v) , vis[v] = 1);
		}
	}

	return dist[T] > -inf;
}

int dfs(int now , int flow)
{
	if(now == T) return flow;
	vis[now] = 1;int ret = 0 , tmp;

	for(int i = st[now] ; i ; i = g[i].nex)
	{
		int v = g[i].to;
		if(vis[v] || !g[i].flow || dist[v] != dist[now] + g[i].val) continue;

		tmp = dfs(v , min(g[i].flow , flow));
		
		if(tmp)
			g[i].flow -= tmp , g[i ^ 1].flow += tmp , flow -= tmp , ret += tmp , ans += 1ll * tmp * g[i].val;
		else
			dist[v] = -inf;
	}

	return ret;
}


int main()
{
	scanf("%d",&n) , S = n << 1 | 1, T = S + 1;

	for(int i = 1 , x , y , t;i <= n;i ++) 
		scanf("%d %d %d",&x,&y,&t) , add_edge(S , i , t , 0) , 
		add_edge(i , T + 1 , t , x + y) , add_edge(i , T + 2 , t , x - y) , 
		add_edge(i , T + 3 , t , -x + y) , add_edge(i , T + 4 , t , -x -y) ;
	for(int i = 1 , x , y , t;i <= n;i ++)
		scanf("%d %d %d",&x,&y,&t) , add_edge(i + n, T , t , 0) , 
		add_edge(T + 1 , i + n , t , -x - y) , add_edge(T + 2 , i + n , t , -x + y) , 
		add_edge(T + 3 , i + n , t , x - y) , add_edge(T + 4 , i + n , t , +x + y);

	while(spfa()) dfs(S , inf);
	printf("%lld\n",ans);

	return 0;
}


Measured memory_bytes: 3552
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define numrep(i,n) for(int i=1;i<=n;i++)
#define bitrep(n) for(int bit=0;bit<(1<<n);bit++)
#define ll int64_t
#define all(v) v.begin(), v.end()

int main() {

int n; cin>>n;

vector<ll> dp(45);
dp[0]=1;
dp[1]=1;

for(int i=2;i<45;i++) dp[i]=dp[i-1]+dp[i-2];

cout << dp[n] << endl;

return 0;
}


Measured memory_bytes: 3092
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define abs (x)(x>0?x:-x)


int main() 
{
	int N;
	int p[100];
	int count = 0;

	scanf("%d", &N);

	for (int i = 0; i < N; i++)
	{
		scanf("%d", &p[i]);
		if (p[i] != i+1)
			count++;
	}

	if (count > 2)
		printf("NO\n");
	else
		printf("YES\n");

	
}

Measured memory_bytes: 128
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		int m=sc.nextInt();
		if(Math.abs(n-m)>1){
			System.out.println(0);
			return;
		}
		int min=Math.min(n,m);
		int max=Math.max(n,m);
		long ans=1;
		long mod=1000000007;
		for(int i=2; i<=max; i++){
			ans*=i;
			ans%=mod;
		}
		for(int i=2; i<=min; i++){
			ans*=i;
			ans%=mod;
		}
		if(n==m){
			ans*=Combination(max+1,min,mod)-max+1;
		}
		System.out.println(ans%mod);
	}
	static long Combination(long left,long right,long mod){
		long ans=1;
		right=Math.min(right,left-right);
		for(int i=0; i<right; i++){
			ans*=(left-i);
			ans%=mod;
		}
		for(int i=2; i<=right; i++){
			long tmp=mod-2;
			long mul=i;
			while(tmp>0){
				if((tmp&1)==1){
					ans*=mul;
				}
				tmp>>=1;
				mul*=mul;
				ans%=mod;
				mul%=mod;
			}
		}
		return ans;
	}
}


Measured memory_bytes: 23764
#include <bits/stdc++.h>
using namespace std;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define all(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)
#define bit(n) (1LL<<(n))
#define bit_exist(x, n) ((x >> n) & 1)
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) cout << #v << "=" << endl; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << endl;
#define mdebug(m) cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;}
#define pb push_back
#define f first
#define s second
#define int long long
#define INF 1000000000000000000
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); i++) { cout << v[i]; if(i != v.size() - 1) cout << endl; }; return os; }
template<typename T> void Out(T x) { cout << x << endl; }
template<typename T1, typename T2> void Ans(bool f, T1 y, T2 n) { if(f) Out(y); else Out(n); }

using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using PiP = pair<int, Pii>;
using PPi = pair<Pii, int>;
using bools = vector<bool>;
using pairs = vector<Pii>;

//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//char d[4] = {'D','R','U','L'};

const int mod = 1000000007;
//const int mod = 998244353;
#define Add(x, y) x = (x + (y)) % mod
#define Mult(x, y) x = (x * (y)) % mod

signed main(){
    int N; cin>>N;
    vector<string> S(N);
    REP(i,N) cin>>S[i];
    Sort(S);
    int ans = 1;
    REP(i,N-1){
        if(S[i]!=S[i+1]){
            ans ++;
        }
    }
    Out(ans);
}

Measured memory_bytes: 9444
from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

n,m = map(int,stdin.readline().rstrip().split())
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]

li.sort()

point = 0
yen = 0

for i in li:
    x,y = i
    if y + point >= m:
        yen += x*(m-point)
        break
    else:
        yen += x*y
        point += y

print(yen)

Measured memory_bytes: 27880
"""
int(input())
map(int,input().split())
list(map(int,input().split()))

"""

n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[]
for i in range(n):
    b.append((a[i]+1)/2)
c=[]
s=sum(b[0:k])
for i in range(k-1,n):
    c.append(s)
    if(i==n-1):
        break
    s=s+b[i+1]-b[i-k+1]

print(max(c))    

Measured memory_bytes: 25060
import qualified Data.ByteString.Char8 as B
import Debug.Trace

f :: B.ByteString -> Bool
f bs
  | len == 0 = False
  | len == 1 = True
  | otherwise = l == r && B.reverse l == l && B.reverse r == r
  where
    len = B.length bs
    (l, r_) = B.splitAt (len `div` 2) bs
    r = B.drop 1 r_
    

main = do
  str <- getLine
  if f (B.pack str)
    then putStrLn "Yes"
    else putStrLn "No"

Measured memory_bytes: 508
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;

namespace ABC129
{
  class Program
  {
    public static void Main(string[] args)
    {
      int[] a = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
      Array.Sort(a);
      Console.WriteLine(a[0] + a[1]);
    }
  }
}

Measured memory_bytes: 11220
N, K = map(int, input().split())
a = list(map(int, input().split()))
 
a = sorted(a)
ans = N
t = 0

for i in range(N-1, -1, -1) :
    if t+a[i] < K :
        t += a[i]
    else :
        ans = min(ans, i)
 
print(ans)

Measured memory_bytes: 9616
#include <bits/stdc++.h>
#define FOR(i, a, n) for(int (i) = (int)(a); (i) < (int)(n); ++(i))
#define FORe(i, a, n) for(int (i) = (int)(a); (i) <= (int)(n); ++(i))
#define rFOR(i, a, n) for(int (i) = (int)(n)-1; (i) >= (int)(a); --(i))
#define rFORe(i, a, n) for(int (i) = (int)(n); (i) >= (int)(a); --(i))
#define REP(i, n) FOR((i), 0, (n))
#define REPe(i, n) FORe((i), 1, (n))
#define REPo(i, n) FORe((i), 0, (n))
#define rREP(i, n) rFOR((i), 0, (n))
#define rREPe(i, n) rFORe((i), 1, (n))
#define rREPo(i, n) rFORe((i), 0, (n))
#define rep(i, n) FOR((i), 0, (n))
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second
#define dup(x, y) (((x)+(y)-1)/(y))
#define vc(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
using ll = long long;
using P = pair<int,int>;
using pll = pair<ll,ll>;
using T = tuple<int,int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vs = vector<string>;
using vp = vector<P>;
using vt = vector<T>;

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

// UnionFind
struct UnionFind {
  vector<int> d;
  UnionFind(int n=0): d(n,-1) {}
  int find(int x) {
    if (d[x] < 0) return x;
    return d[x] = find(d[x]);
  }
  bool unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return false;
    if (d[x] > d[y]) swap(x,y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y) { return find(x) == find(y);}
  int size(int x) { return -d[find(x)];}
};

int main() {
  int n,m;
  cin>>n>>m;
  UnionFind uf(n);
  REP(i, m) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    uf.unite(a,b);
  }
  int ans = 0;
  REP(i, n) {
    chmax(ans, uf.size(i));
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 4028
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#define int long long
using namespace std;
signed main() {
	int n; cin >> n;
	int a[123456];
	int m = 0, M = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		if (!i) {
			m = a[i]; M = a[i];
		}
		else {
			m = min(m, a[i]);
			M = max(M, a[i]);
		}
	}
	if (M - m > 1) {
		cout << "No\n";
		return 0;
	}
	else if (m == M)cout << (M == n - 1 || M * 2 <= n ? "Yes\n" : "No\n");
	else {
		int s = 0;
		for (int i = 0; i < n; i++)if (a[i] == m)s++;
		cout << ((s <= m && M <= s + (n - s) / 2) ? "Yes\n" : "No\n");
	}
	return 0;
}

Measured memory_bytes: 1024
//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#define MOD 1000000007
#define INF (1LL<<30)
#define LLINF (1LL<<60)
#define PI 3.14159265359
#define EPS 1e-12
//#define int ll

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

int p[10][10], q[10][10], h, w, c, res = 0;
bool used[10][10];
void dfs(int x, int y, int co) {
	//cout << "xy:" << x << " " << y << endl;
	used[y][x] = true;
	REP(i, 4) {
		int nx = x+dx[i], ny = y+dy[i];
		if(IN(0, w, nx) && IN(0, h, ny) && !used[ny][nx] && q[y][x] == q[ny][nx]) {
			dfs(nx, ny, co);
		}
	}
	q[y][x] = co;
}

void dfs1(int x, int y, int co) {
	//cout << x << " " << y << endl;
	used[y][x] = true;
	REP(i, 4) {
		int nx = x+dx[i], ny = y+dy[i];
		if(IN(0, w, nx) && IN(0, h, ny) && !used[ny][nx] && q[y][x] == q[ny][nx]) {
			dfs1(nx, ny, co);
			res++;
		}
	}
}

signed main(void)
{
	while(true) {
		cin >> h >> w >> c;
		if(!h && !w && !c) break;
		REP(i, h) REP(j, w) cin >> p[i][j];
		int ans = -INF;
		FOR(i1, 1, 7) FOR(i2, 1, 7) FOR(i3, 1, 7) FOR(i4, 1, 7) {
			//cout << "i:" << i1 << " " << i2 << " " << i3 << " " << i4 << endl;
			REP(i, h) REP(j, w) q[i][j] = p[i][j];
			//cout << "a" << endl;
			REP(i, h) REP(j, w) used[i][j] = false;
			dfs(0, 0, i1);
			/*REP(i, h) {
				REP(j, w) {
					cout << q[i][j] << " ";
				}
				cout << endl;
			}*/
			//cout << "b" << endl;
			REP(i, h) REP(j, w) used[i][j] = false;
			dfs(0, 0, i2);
			/*REP(i, h) {
				REP(j, w) {
					cout << q[i][j] << " ";
				}
				cout << endl;
			}*/
			//cout << "c" << endl;
			REP(i, h) REP(j, w) used[i][j] = false;
			dfs(0, 0, i3);
			/*REP(i, h) {
				REP(j, w) {
					cout << q[i][j] << " ";
				}
				cout << endl;
			}*/
			//cout << "d" << endl;
			REP(i, h) REP(j, w) used[i][j] = false;
			dfs(0, 0, i4);
			/*REP(i, h) {
				REP(j, w) {
					cout << q[i][j] << " ";
				}
				cout << endl;
			}*/
			//cout << "e" << endl;
			REP(i, h) REP(j, w) used[i][j] = false;
			dfs(0, 0, c);
			//cout << "f" << endl;
			//if(i1 == 6 && i2 == 3 && i3 == 4 && i4 == 2) {
				/*REP(i, h) {
					REP(j, w) {
						cout << q[i][j] << " ";
					}
					cout << endl;
				}*/
			//}
			REP(i, h) REP(j, w) used[i][j] = false;
			res = 1;
			dfs1(0, 0, c);
			ans = max(ans, res);
			//cout << "ans:" << ans << endl;
		}
		cout << ans << endl;
	}

	return 0;
}

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

#define forn(i,n) for (int i = 0; i < int(n); i++)

const int MOD = 998244353;
const int N = 1e4 + 10;
typedef long long ll;

int n, dp[N][N], inv[N], fact[N], ifact[N];
string a,b;

void add(int &x, int y) {
    x += y;
    if (x >= MOD) x -= MOD;
}

int main() {

    inv[1] = 1;
    for (int n = 2; n < N; n++) {
        inv[n] = ll(MOD - MOD/n) * inv[MOD%n] % MOD;
        assert(ll(n) * inv[n] % MOD == 1);
    }
    fact[0] = ifact[0] = 1;
    for (int n = 1; n < N; n++) {
        fact[n] = (ll) n * fact[n-1] % MOD;
        ifact[n] = (ll) inv[n] * ifact[n-1] % MOD;
    }

    cin >> a >> b;
    n = a.size();

    int x = 0, y = 0;
    forn(i,n) if (a[i] == '1') {
        if (b[i] == '0') y++;
        else x++;
    }

    forn(i,x+1) forn(j,y+1) {
        if (i == 0 && j == 0) dp[i][j] = 1;
        else {
            dp[i][j] = 0;
            if (i && j) add(dp[i][j], (ll) dp[i-1][j] * i%MOD * j%MOD);
            if (j) add(dp[i][j], (ll) dp[i][j-1] *j%MOD *j%MOD);
        }
    }

    int coef = 1, ans = 0;
    forn(k,x+1) {
        add(ans, (ll) coef * dp[x-k][y] % MOD);
        coef = (ll) coef * (x-k) % MOD;
        coef = (ll) coef * (x+y-k) % MOD;
    }
    cout << ans << endl;

    return 0;
}


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

const int MAX = 210000;
const int MOD = 1000000007;

long long int fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

long long int COM(long long int n, long long int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    long long int x = finv[k] % MOD;
    for (long long int i = n; i > n - k; i--) {
      x = i * x % MOD;
    }
    return x;
}

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

int main() {
  long long int n, a, b;
  cin >> n >> a >> b;
  COMinit();
  long long int x = (modpow(2, n) - COM(n, a) - COM(n, b) - 1 + 2*MOD) % MOD;
  if (x >= 0) cout << x << endl;
  else cout << MOD + x << endl;
}



Measured memory_bytes: 5120
using System;
using System.Linq;
using System.Collections.Generic;

namespace HelloWorld
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            var list = new List<long>();
            list = Console.ReadLine().Split(' ').Select(long.Parse).ToList();
            Console.WriteLine("{0} {1} {2}", list.Min(), list.Max(), list.Sum());
        }
    }
}


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

int main() {
  vector<vector<int>> a(3,vector<int>(3));
  for(int i=0; i<3; i++){
    for(int j=0; j<3; j++){
      cin>>a[i][j];
    }
  }
  int n,b[105];
  cin>>n;
  for(int i=0; i<n; i++) cin>>b[i];
  for(int i=0; i<3; i++){
    for(int j=0; j<3; j++){
       for(int k=0; k<n; k++){
         if(a[i][j] == b[k]) a[i][j]=0;
       }
    }
  }
  bool can = true;
  for(int i=0; i<3; i++){
    for(int j=0; j<3; j++){
   		if(a[i][j]!=0) can = false;
    	if(j==2 && can) {
      		cout<<"Yes";
      		return 0;
    	}
    }
    can = true;
  }
  for(int i=0; i<3; i++){
    for(int j=0; j<3; j++){
   		if(a[j][i]!=0) can = false;
    	if(j==2 && can) {
      		cout<<"Yes";
      		return 0;
    	}
    }
    can = true;
  }
  if(a[0][0]==0 && a[1][1]==0 && a[2][2] ==0) {
    cout<<"Yes";
    return 0;
  }
  if(a[0][2]==0 && a[1][1]==0 && a[2][0] == 0) {
    cout<<"Yes";
    return 0;
  }
  cout<<"No";
}

Measured memory_bytes: 256
n, m = map(int, input().split())
result = []

problems = [False for _ in range(n)]
problems_end = [True for _ in range(n)]
wa_count = 0

for i in range(m):
    s = list(input().split(' '))
    if s[1] == 'AC':
        problems[int(s[0])-1] = True
    result.append(s)



for i, j in result:
    if j == 'AC':
        problems_end[int(i)-1] = False
    if problems[int(i)-1] == True and j == 'WA' and problems_end[int(i)-1] == True:
        wa_count += 1

ac_count = problems.count(True)
print(ac_count, wa_count)





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


int sum_of_digits(int num)
{
	int sum = 0;
	while (num > 0)
	{
		sum += num%10;
		num /= 10;
	}
	return sum;
}

int main()
{
	int n,a,b; cin >>n>>a>>b;
	int ans = 0;
	for (int i = 1; i <= n; ++i)
	{
		int x = sum_of_digits(i);
		if (a <= x && x <= b)
			ans += i;
	}
	cout << ans << endl;
}



Measured memory_bytes: 3628
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <set>
#include <tuple>
#include <unordered_set>
using namespace std;
#define int long long
set<tuple<int, int, int> > done;
int D;
int ds[365];

int dfs(int cl, int d, int cnt) {
	if(d < D && (cl & ds[d])) return 0;
	auto v = make_tuple(cl, d, cnt);
	if(done.count(v)) return 0;
	done.insert(v);
	for(int i = 0; i < 16; i++) {
		int c = (cnt >> (i * 3)) & 7;
		cnt ^= c << (i * 3);
		if(cl & (1LL << i)) c = 0;
		else c++;
		if(c == 7) return 0;
		cnt ^= c << (i * 3);
	}
	if(d == D) return 1;

	for(int i = 0; i < 2; i++) {
		if(dfs(cl, d + 1, cnt)) return 1;
		if(!((4369 << i) & cl) && dfs(cl >> (i + 1), d + 1, cnt)) return 1;
		if(!((34952 >> i) & cl) && dfs(cl << (i + 1), d + 1, cnt)) return 1;
		if(!((15 << (i * 4)) & cl) && dfs(cl >> ((i + 1) * 4), d + 1, cnt)) return 1;
		if(!((61440 >> (i * 4)) & cl) && dfs(cl << ((i + 1) * 4), d + 1, cnt)) return 1;
	}
	return 0;
}

void solve() {
	for(int i = 0; i < D; i++) {
		ds[i] = 0;
		for(int j = 0; j < 16; j++) {
			int a;
			cin >> a;
			ds[i] |= a << j;
		}
	}
	done.clear();

	cout << dfs(1632, 0, 0) << endl;
}

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

	while(cin >> D, D) {
		solve();
	}
}

Measured memory_bytes: 26880
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
B.append(0)

diff, old_diff, B_sum = [0, 0, 0]
for i in range(N+1):
  if old_diff > A[i]:
    old_diff = A[i]
  diff = B[i] - A[i] + old_diff
  if diff < 0:
    diff = 0
    B_sum = B_sum + B[i] + old_diff
  else:
    B_sum = B_sum + A[i]
  old_diff = diff
    
print(B_sum)
    

Measured memory_bytes: 19116
# include "algorithm"
# include "iostream"
# include "cstdio"
# define lowbit(x) (x&-x)

using namespace std;

const int maxm=3e5+10;

int N,M,Tree[maxm],Ans[maxm];

struct line{
	int L;
	int R;
	int Len;
	# define L(x) Line[x].L
	# define R(x) Line[x].R
	# define Len(x) Line[x].Len
}Line[maxm];

inline bool Comp(line x,line y){
	return x.Len<y.Len;
}

inline void Update(int x,int Value){
	while(x<=M){
		Tree[x]+=Value;
		x+=lowbit(x);
	}
	return;
}

inline int Ask(int x){
	register int Result=0;
	while(x){
		Result+=Tree[x];
		x-=lowbit(x);
	}
	return Result;
}

int main(){
	register int i,j,k,Add,Now;
	scanf("%d%d",&N,&M);
	Add=N;
	for(i=1;i<=N;i++){
		scanf("%d%d",&L(i),&R(i));
		Len(i)=R(i)-L(i)+1;
		Update(L(i),1);
		Update(R(i)+1,-1);
	}
	sort(Line+1,Line+1+N,Comp);
	for(i=M;i;i--){
		for(Add;Len(Add)>=i;Add--){
			Update(L(Add),-1);
			Update(R(Add)+1,1);
		}
		Now=N-Add;
		for(j=i;j<=M;j+=i){
			Now+=Ask(j);
		}
		Ans[i]=Now;
	}
	for(i=1;i<=M;i++){
		printf("%d\n",Ans[i]);
	}
	return 0;
}

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

using namespace std;

int main() {
    int N = 0;
    cin >> N;
    int ans = 0;
    vector<int> A(N,0);
    for(int i = 0; i < N; i++) {
    cin >> A.at(i);
    if (A.at(i)%2)
    {
        ans++;
    }
    
    }
    if(ans%2) {
    cout << "NO" << endl;
    } else {
    cout << "YES" << endl;
    }

    return 0;
}

Measured memory_bytes: 3788
#include<cmath>
#include<queue>
#include<cstdio>

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

using namespace std;

const double oo=1e77;
const double EPS=1e-8;

template<class T>
struct point{
	T x,y;
	point &operator+=(const point &a){ x+=a.x; y+=a.y; }
	point &operator-=(const point &a){ x-=a.x; y-=a.y; }
	point operator+(const point &a)const{ return (point){x+a.x,y+a.y}; }
	point operator-(const point &a)const{ return (point){x-a.x,y-a.y}; }
};

template<class T>
T cross(const point<T> &a,const point<T> &b){ return a.x*b.y-a.y*b.x; }

template<class T>
struct segment{ point<T> a,b; };

enum {CCW=1,CW=-1,ON=0};
int ccw(const point<double> &a,const point<double> &b,const point<double> &c){
	double rdir=cross(b-a,c-a);
	if(rdir> EPS) return CCW;
	if(rdir<-EPS) return CW;
	return ON;
}

bool intersect(const segment<double> &S1,const segment<double> &S2){
	if(max(S1.a.x,S1.b.x)+EPS<min(S2.a.x,S2.b.x)
	|| max(S1.a.y,S1.b.y)+EPS<min(S2.a.y,S2.b.y)
	|| max(S2.a.x,S2.b.x)+EPS<min(S1.a.x,S1.b.x)
	|| max(S2.a.y,S2.b.y)+EPS<min(S1.a.y,S1.b.y)) return false;
	return ccw(S1.a,S1.b,S2.a)*ccw(S1.a,S1.b,S2.b)<=0
		&& ccw(S2.a,S2.b,S1.a)*ccw(S2.a,S2.b,S1.b)<=0;
}

double solve(int na,const int *xa,const int *ya,int nb,const int *xb,const int *yb){
	double d[1000];
	rep(i,na) d[i]=(i==0?0:oo);

	priority_queue< pair<double,int> > Q;
	Q.push(make_pair(0,0));
	while(!Q.empty()){
		double d_now=-Q.top().first;
		int i=Q.top().second; Q.pop();

		if(d[i]<d_now-EPS) continue;

		rep(j,na) if(!intersect((segment<double>){(point<double>){xa[i],ya[i]},(point<double>){xa[j],ya[j]}},(segment<double>){(point<double>){xb[0],yb[0]},(point<double>){xb[1],yb[1]}})) {
			double d_next=d_now+hypot(xa[i]-xa[j],ya[i]-ya[j]);
			if(d[j]>d_next+EPS){
				d[j]=d_next;
				Q.push(make_pair(-d_next,j));
			}
		}
	}
	return d[1]+hypot(xb[0]-xb[1],yb[0]-yb[1]);
}

int main(){
	int na,nb; scanf("%d%d",&na,&nb);
	int xa[1000],ya[1000],xb[1000],yb[1000];
	rep(i,na) scanf("%d%d",xa+i,ya+i);
	rep(i,nb) scanf("%d%d",xb+i,yb+i);

	double ans=min(solve(na,xa,ya,nb,xb,yb),solve(nb,xb,yb,na,xa,ya));
	printf("%.15f\n",ans<oo/2?ans:-1);

	return 0;
}

Measured memory_bytes: 1224
#include<bits/stdc++.h>
using namespace std;
#define N 109
#define ll long long
int n, w, wt[N], v[N];
ll dp[N][100009];

ll solve(int i, int c)
{
    if(i > n) return 0;
    if(dp[i][c] != -1) return dp[i][c];
    ll ans = 0;
    if(c - wt[i] >= 0) ans = solve(i + 1, c - wt[i]) + (ll)v[i];
    ans = max(ans, solve(i + 1, c));
    return dp[i][c] = ans;
}

int main()
{
    memset(dp, -1, sizeof(dp));
    cin >> n >> w;
    for(int i = 1; i <= n; i++) cin >> wt[i] >> v[i];
    cout << solve(1, w) << endl;
}


Measured memory_bytes: 85376
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
#define int long long  
signed main(){
    int N;
    int Ans=0;
    int a[114514];
    cin >> N;
    REP(i,N){cin >> a[i];}
    REP(i,N){
        if(a[a[i]-1]-1==i){
            Ans++;
        }
    }
    cout << Ans/2 << endl;
	return 0;
}


Measured memory_bytes: 1024
/** 
 * Dont raise your voice, improve your argument.
 * --Desmond Tutu
 */

#include <bits/stdc++.h>
using namespace std;

#define DEBUG
#ifndef DEBUG
#define endl "\n"
#endif

const double PI=3.1415926535897932384626433;
typedef long long ll;
#define fori(n) for(ll i=0; i<(n); i++)

#define cins(s) string s; cin>>s;
#define cini(i) int i; cin>>i;
#define cinll(l) ll l; cin>>l;
#define cind(d) double d; cin>>d;
#define cinai(a, n) vi a(n); fori(n) { cin>>a[i]; }
#define cinall(a, n) vll a(n); fori(n) { cin>>a[i]; }
#define cinas(s, n) vs s(n); fori(n) { cin>>s[i]; }

typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef pair<double,double> pdd;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<string> vs;
typedef vector<ll> vll;


void solve() {
    cini(H);
    cini(W);
    vvi a(H, vi(W));
    vvi b(H, vi(W));
    vvi c(H, vi(W));
    for(int i=0; i<H; i++)
        for(int j=0; j<W; j++) 
            cin>>a[i][j];
    for(int i=0; i<H; i++)
        for(int j=0; j<W; j++)  {
            cin>>b[i][j];
        }

    const int OFFS=80*160+1;

    vvvb dp(H, vvb(W, vb(OFFS*2)));
    dp[0][0][a[0][0]-b[0][0]+OFFS]=true;
    dp[0][0][b[0][0]-a[0][0]+OFFS]=true;

    for(int i=0; i<H; i++) {
        for(int j=0; j<W; j++) {
            for(int k=0; k<OFFS*2; k++) {
                if(dp[i][j][k]) {
                    if(i+1<H) {
                        int val=a[i+1][j]-b[i+1][j];
                        dp[i+1][j][k+val]=true;
                        dp[i+1][j][k-val]=true;
                    }
                    if(j+1<W) {
                        int val=a[i][j+1]-b[i][j+1];
                        dp[i][j+1][k+val]=true;
                        dp[i][j+1][k-val]=true;
                    }
                }
            }
        }
    }

    int ans=1e9;
    for(int i=0; i<OFFS*2; i++)
        if(dp[H-1][W-1][i])
            ans=min(ans, abs(i-OFFS));

    cout<<ans<<endl;
}

int main() {
cin.tie(nullptr);
std::ios::sync_with_stdio(false);
        solve();
}



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

int main() {
  int N,A,B;
  cin >> N >> A >> B;
  
  if ( N * A > B ) {
    cout << B << endl;
  }
  
  else if (N * A < B ) {
    cout << N * A << endl;
  }
  
  else {
    cout << B << endl;
  }
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

enum
{
  SIMPLE = 1,
  COMPOUND = 2
};

int
main (
  int   argc,
  char *argv[ ]
  )
{
  for ( ; ; )
  {
    int res = -1;
    double mag = 0;
    int n, y;

    scanf ( "%d", &n );
    if ( n == 0 ) break ;
    scanf ( "%d", &y );
    while ( n-- )
    {
      double m;
      int b, r, t;

      scanf ( "%d%d%d", &b, &r, &t );
      switch ( t )
      {
        case SIMPLE:
          m = ( 100 + y * r ) / 100.;
          break ;
        case COMPOUND:
          m = pow ( ( 100 + r ) / 100., y );
          break ;
      }

      if ( m > mag )
      {
        res = b;
        mag = m;
      }
    }

    printf ( "%d\n", res );
  }

  return ( EXIT_SUCCESS );
}

Measured memory_bytes: 692
using System;
using System.Collections.Generic;
using static System.Console;
using System.Linq;
using System.IO;

namespace ConsoleApp2
{
    class Program {
        static decimal C(int a,int b) {
            decimal res = 1;
            for (int i = 0; i < b; i++) {
                res *= (a - i);
                res /= (i + 1);
            }
            return res;
        }


        static void Main(string[] Args) {
            var lis = new List<string>(ReadLine().Split(' ')).Select(int.Parse).ToList();

            if (lis[0] + lis[1] >= lis[2] && lis[0] + lis[2] >= lis[1])
                WriteLine(0);
            else
                WriteLine(
                    Math.Min(
                        Math.Max(Math.Abs(lis[2] - lis[1] - lis[0]), 0),
                        Math.Max(Math.Abs(lis[1] - lis[0] - lis[2]), 0)
                        )
                    );
            

            ProgramEndPointLabel:;

            ReadLine();
        }
    }
}


Measured memory_bytes: 11732
#include <iostream>
#include <algorithm>
using namespace std;
const int INF=998244353;
int n;
int d[100000];
int x[100000];
int m=0;
int main(){
    cin>>n;
    for(int i=0;i<n;i++)cin>>d[i],x[d[i]]++,m=max(m,d[i]);
    if(d[0]!=0||x[0]!=1){
        cout<<0;
        return 0;
    }
    long long ans=1LL;
    for(int i=1;i<=m;i++){
        if(x[i]==0){
            cout<<0<<endl;
            return 0;
        }
        for(int j=0;j<x[i];j++)ans*=x[i-1],ans%=INF;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cmath>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <string>

using namespace std;

typedef long long LL;
typedef unsigned int UI;

#define rSort(a) 		sort(a.rbegin(),a.rend())
#define Sort(a) 		sort(a.begin(),a.end())
#define Reverse(a) 		reverse(a.begin(),a.end())
#define Sum(a)  		accumulate(a.begin(), a.end(), 0)
#define REP(i, n) 		for(UI i = 0;i < n;i++)
#define REPR(i, n) 		for(UI i = n;i >= 0;i--)
#define FOR(i, m, n) 	for(UI i = m;i < n;i++)
#define pb(i) 			push_back(i)
#define SWAP(x,y) 		((x!=y)&&(x^=y,y^=x,x^=y))

#define MOD  			(LL)1e9 + 7;
#define INF  			(LL)1 << 62;

int main(int argc, char* argv[]) {

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

	LL W, H, N;
	LL ans;

	cin >> W >> H >> N;

	vector < vector < int >> S(H, vector<int>(W, 0));
	vector<int>x(N);
	vector<int>y(N);
	vector<int>a(N);

	for (int i = 0; i < N; i++) {
		cin >> x[i] >> y[i] >> a[i];
		switch (a[i]) {
		case 1:
			for (int j = 0; j < H; j++) {
				for (int k = 0; k < x[i]; k++) {
					S[j][k] = 1;
				}
			}
			break;

		case 2:
			for (int j = 0; j < H; j++) {
				for (int k = x[i]; k < W; k++) {
					S[j][k] = 1;
				}
			}
			break;

		case 3:
			for (int j = 0; j < y[i]; j++) {
				for (int k = 0; k < W; k++) {
					S[j][k] = 1;
				}
			}
			break;

		case 4:
			for (int j = y[i]; j < H; j++) {
				for (int k = 0; k < W; k++) {
					S[j][k] = 1;
				}
			}
			break;

		default:
			break;

		}
	}

	ans = W * H;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (S[i][j] == 1) {
				ans--;
			}
		}
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256