akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define MOD (1000000007)
#define vi vector<int>
#define vvi vector<vi>
#define all(a)  (a).begin(),(a).end()

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

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

const ll INF = 1LL << 60;

int main(){
  int n; cin >> n;
  vi a(n); rep(i, n) cin >> a[i];

  int right = 0;
  ll sum = 0, ans = 0;
  rep(left, n){
    while(right < n && (sum ^ a[right]) == (sum + a[right])){
      sum += a[right];
      right++;
    }
    ans += right - left;

    if(right == left) right++;
    else sum -= a[left];
  }
  std::cout << ans << '\n';
}


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

using namespace std;
#define ll               long long
#define dl               double
#define ull              unsigned long long
#define ft               first
#define sd               second
#define pi               acos(-1)
#define ct(tc)           scanf("%lld",&tc)
#define scnm(n,m)        scanf("%lld %lld",&n,&m);
#define max3(a,b,c)      max(a,max(b,c))
#define max4(a,b,c,d)    max(a,max(b,max(c,d)))
#define min3(a,b,c)      min(a,min(b,c))
#define min4(a,b,c,d)    min(a,min(b,min(c,d)))
#define pb               push_back
#define srt              sort(v.begin(),v.end())
#define rsrt             reverse(v.begin(),v.end())
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll m;
    scanf("%lld",&m);
    ll fh,f,hc;
    //code sumu
    fh=m/500;
    f=((m%500)/5);
    hc=((fh*1000)+(f*5));
    printf("%lld\n",hc);
    return 0;

}




Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <tuple>
#include <climits>
#include <cmath>
#include <unordered_map>

using namespace std;

typedef long long ll;

int main(void) {
  ll N, K;
  string S;
  cin >> N >> S >> K;

  for (int i = 0; i < N; i++) {
    cout << (S[i] != S[K - 1] ? '*' : S[i]);
  }
  cout << endl;
}


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

int main() {
	
	int n;
	cin >> n;
	int arr[n];
	for (int i=0; i<n; i++) {
		cin >> arr[i];
	}
	int dp[n];
	dp[n-1] = 1;
	for (int i=n-2; i>=0; i--) {
		if (arr[i] >= arr[i+1]) {
			dp[i] = dp[i+1] + 1;
		}
		else {
			dp[i] = 1;
		}
	}
	
	int mx = 0;
	for (int i=0; i<n; i++) {
		mx = max(mx, dp[i]);
	}
	
	cout << mx - 1 << endl;
	
}


Measured memory_bytes: 1024
#!/usr/bin/env python3
import sys


def solve(N: int):
    print(N * 2 if N % 2 else N)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
/*

*/
#include<iostream>
#include<iomanip>
#include<ios>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<algorithm>
#include<utility>
#include<math.h>
#include<cstdlib>
#define rep(i, n) for(int i=0;i<n;i++)
#define repb(i, a, b) for(int i=a;i<b;i++)
#define MAX_N 10000

using namespace std;
typedef pair<int, int> P;
typedef long long int ll;

const int INF = 1<<30;
const ll MOD = ll(1e9+7);

int main(){
  int l, r, d;cin>>l>>r>>d;
  cout<<(r/d)-((l-1)/d)<<endl;
  // system("read -n 1 -s -p \"Press any key to continue...\"");
}


Measured memory_bytes: 3620
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdlib>
#include<utility>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define pi acos(-1)
#define pb push_back
using namespace std;
typedef pair<int,int> p;
typedef long long ll;

int main(){
	string s;
	cin>>s;
	bool check=false;
	rep(i,s.size()){
		if(s[i]=='9'){
			check=true;
			break;
		}
	}
	cout<<((check)?"Yes":"No")<<endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        q_1();
    }

    private static void q_1() {
        try(Scanner scan = new Scanner(System.in)) {
            int H = scan.nextInt();
            int W = scan.nextInt();
            int h = scan.nextInt();
            int w = scan.nextInt();

            int result = (H * W) - ((W * h) - (h * w) + (H * w));

            System.out.println(result);
        }
    }
}

Measured memory_bytes: 22612
/* Atcoder abc166a
 * See tasks at: https://atcoder.jp/contests/abc166/tasks/abc166_a
 */
#include <bits/stdc++.h>

#define until(symbol, max) for (int symbol = 0; (symbol) < (max); (symbol)++)

using namespace std;
using ll = long long;
int main()
{
    string s;
    cin >> s;

    if (s == "ABC")
    {
        cout << "ARC";
    }
    else
    {
        cout << "ABC";
    }
    
    return 0;
}


Measured memory_bytes: 3512
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define int ll
#define pb push_back
#define setbits(x)          __builtin_popcountll(x)
#define endl "\n"
typedef long long ll;
vector<int> find(int n)
{
    vector<int> ans;
    for(int i=1;i*i<=n;i++)
    {
        if(n%i==0)
        {
            ans.pb(i);
            if(n/i!=i)
                ans.pb(n/i);
        }
    }
    return ans;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin>>n;
int arr[n];

unordered_map<int,int> dp;
int ans=0;
for(int i=0;i<n;i++)
    cin>>arr[i];
    for(int i=0;i<n;i++)
        dp[arr[i]]+=1;
        unordered_map<int,int> mp;
        sort(arr,arr+n);
    for(int i=0;i<n;i++)
    {int ok=1;
        int res=0;
            vector<int> a=find(arr[i]);
            for(int j=0;j<a.size();j++)
            {if(mp[a[j]])
            ok=0;
            ///mp[a[j]]=1;
            }
            ///ans+=n-res;

        mp[arr[i]]=1;
        if(ok&&dp[arr[i]]==1)
            ans++;
    }

    cout<<ans<<endl;
    return 0;
}


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

int main(){
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int score = 0;
    rep(i,n-1){
        if(s[i] == s[i+1]) score++;
    }
    int ans = min(score+2*k, n-1);
    cout << ans << endl;
}

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

const int INF = 1e9;

int main() {
  int n, k;
  cin >> n >> k;
  
  int mn = INF;
  for (int i = 0; i < n; ++i) {
    int a, b;
    cin >> a >> b;
    if (b > k) continue;
    mn = min(mn, a);
  }
  if (mn == INF) {
    cout << "TLE" << endl;
  } else {
    cout << mn << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <stack>
#include <string>
#include <cstdlib>
using namespace std;

int main() {
    stack<int> st;
    int a, b;
    string str;
    while (cin >> str) {
        if (str == "+") {
            b = st.top();
            st.pop();
            a = st.top();
            st.pop();
            st.push(a + b);
        } else if (str == "-") {
            b = st.top();
            st.pop();
            a = st.top();
            st.pop();
            st.push(a - b);
        } else if (str == "*") {
            b = st.top();
            st.pop();
            a = st.top();
            st.pop();
            st.push(a * b);
        } else {
            st.push(atoi(str.c_str()));
        }
    }

    cout << st.top() << endl;
    return 0;
}


Measured memory_bytes: 3184
#include<stdio.h>
#include<math.h>
int main(void){
    int N,K;
    scanf("%d %d",&N,&K);
    int count = 0;
  	long int x=0;
  	x = N;
    while(x>=0){
      x = (long int)(x/K);
      if(x==0){
      	break;
      }
        count++;
    }
  	count++;
    printf("%d",count);
    return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
#define N 9

int board[N];
int rows = 3, cols = 3, zeroIndex;

int blindSearch(int x, int y, int moves, int previousMove) {
  int i,foundAnswer;
  if (moves < (x+y))
    return 0;

  if (!moves) {
    for (i = 0; i < N - 1; i++) {
      if (board[i] != i + 1)
        return 0;
    }

    return 1;
  }

  if (x > 0 && previousMove != 1){
    board[zeroIndex] = board[zeroIndex + rows];
    zeroIndex += rows;

    foundAnswer = blindSearch(x - 1, y, moves - 1, 0);
    if (foundAnswer)
      return 1;

    board[zeroIndex] = board[zeroIndex - rows];
    zeroIndex -= rows;
  }

  if (y > 0 && previousMove != 3) {
    board[zeroIndex] = board[zeroIndex + 1];
    zeroIndex++;

    foundAnswer = blindSearch(x, y - 1, moves - 1, 2);
    if (foundAnswer)
      return 1;

    board[zeroIndex] = board[zeroIndex - 1];
    zeroIndex--;
  }

  if (y < rows - 1 && previousMove != 2){
    board[zeroIndex] = board[zeroIndex - 1];
    zeroIndex--;

    foundAnswer = blindSearch(x, y + 1, moves - 1, 3);
    if (foundAnswer)
      return 1;

    board[zeroIndex] = board[zeroIndex + 1];
    zeroIndex++;
  }

  if (x < cols - 1 && previousMove != 0) {
    // up
    board[zeroIndex] = board[zeroIndex - rows];
    zeroIndex -= rows;

    foundAnswer = blindSearch(x + 1, y, moves - 1, 1);
    if (foundAnswer)
      return 1;

    board[zeroIndex] = board[zeroIndex + rows];
    zeroIndex += rows;
  }

  return 0;
}

int main() {
  int i, x, y, j;

  for (i = 0; i < N; i++) {
    scanf("%d", &board[i]);
    if (!board[i])
      zeroIndex = i;
  }

  x = cols - (zeroIndex / rows) - 1;
  y = rows - (zeroIndex % cols) - 1;

  for (j = 0; j < 50; j++) {
    if (blindSearch(x,y,j,-1)) {
      printf("%d\n", j);
      return 0;
    }
  }
}



Measured memory_bytes: 2108
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include <map>
#include <fstream>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <assert.h>
#include <complex>
using namespace std;
#define eps 0.000001
#define LONG_INF 10000000000000000
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define MOD 998244353
#define seg_size 65536*16
#define REP(i,n) for(long long i = 0;i < n;++i)
int main(){
	double x, t;
	cin >> x >> t;
	cout << x / t << endl;
	return 0;
}

Measured memory_bytes: 256
list=[1]*45

n=int(input())
def fib(n):
    if n==0 or n==1:
        return list[n]
    else:
        if list[n]==1:
            list[n]=fib(n-1)+fib(n-2)
            return list[n]
        else:
            return list[n]
      
print(fib(n))



Measured memory_bytes: 5600
#include <iostream>
#include <set>
#include <string>

using namespace std;

const long MOD = 1000000007;
typedef pair<int, int> P;
typedef long long ll;

int main(){
    string s;
    cin >> s;
    int K;
    cin >> K;

    set<string> stset;
    for(int i=0; i<s.length(); i++){
        for(int l=1; l<=5; l++){
            if(i+l > s.length()) continue;
            string t = s.substr(i, l);
            stset.insert(t);
        }
    }

    int cnt = 1;
    for(auto st : stset){
        if(cnt == K){
            cout << st << endl;
            break;
        }
        cnt++;
    }


    return 0;
}


Measured memory_bytes: 1664
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i< (n);i++)
#define rep1(i,n) for(int i=1;i<= (n);i++)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;

const static ll MOD = 2019;

ll modpow(ll a,ll n){
    if(n==0)return 1;
    if(n%2==1)return a*modpow(a,n-1)%MOD;
    ll t = modpow(a,n/2) % MOD;
    return t*t % MOD;
}

int main(){
    string S;cin>>S;
    ll n = S.size();
    vector<int> T(n+1,0);
    //T[i]に、i文字目までのmodを入れておく.
    //後ろから入れていく(T[n-1] == 0)ことで、T[i] = T[i-1] + S[i]*10**n-i-1とDPで計算できる.
    for(int i = n-1;i>-1;i--){
        T[i] = T[i+1] + (S[i]-'0') * modpow(10,n-i-1);
        T[i] %= MOD;
    }
    map<int,int> mp;
    rep(i,n+1){
        mp[T[i]]++;
    }
    ll ans = 0;
    for(auto it = mp.begin();it != mp.end();it++){
        ll m = it->second;
        ans += m*(m-1)/2;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 4360
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String in = sc.next();
		int k = sc.nextInt();
		
		String s[] = new String[in.length()];
		
		for(int i=0;i<s.length;i++){
			s[i] = in.substring(i);
		}
		
		Arrays.sort(s);
		
		int p = 0;
		while(k>0){
			int skip = 0;
			if(p>0){
				while(skip < s[p-1].length() && s[p].charAt(skip) == s[p-1].charAt(skip))
					skip++;
			}
			
			if(s[p].length() - skip >= k){
				System.out.println(s[p].substring(0, skip+k));
			}
			
			k -= s[p].length() - skip;
			p++;
		}

	}

}


Measured memory_bytes: 53708
N, P = map(int, input().split())
A = list(map(int, input().split()))

B = [A[i] % 2 for i in range(len(A))]
I, O = 0, 0
for i in range(len(B)):
  if B[i] == 1:
    I += 1
  else:
    O += 1
def fact(n):
  L = [1]
  for f in range(n):
    L.append(L[f]*(f+1))
  return L[n]
def nCr(n, r):
  return fact(n) // (fact(r) * fact(n-r))
S = 0
if P == 1:
  for q in range(1, I+1, 2):
    S += nCr(I, q)
elif P == 0:
  for q in range(0, I+1, 2):
    S += nCr(I, q)
print(S * 2 ** O)

Measured memory_bytes: 3064
N,K = map(int,input().split())
A = list(map(int,input().split()))
# firstが負けの状態を押し付け続けることが可能ならば勝ち
dp = [False]*(K+1)
# dp[i](0,A[0]) = False 
for i in range(K):
    if not dp[i]:
        for a in A:
            if i+a <= K:
                dp[i+a] = 1
print("First" if dp[K] else "Second")

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

int main()
{
  int a, b;
  cin >> a >> b;
  int amin = a * 12.5 + 0.5;
  int amax = (a + 1) * 12.5 - 0.5;
  int bmin = b * 10;
  int bmax = bmin + 9;
  if (amax < bmin || bmax < amin)
  {
    cout << -1 << endl;
    return 0;
  }
  cout << max(amin, bmin) << endl;
  return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstring>
#include <chrono>
#include <complex>
#define endl "\n"
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define vvi vector < vi >
#define pii pair<int,int>
#define pll pair<long long, long long>
#define mod 1000000007
#define inf 1000000000000000001;
#define all(c) c.begin(),c.end()
#define mp(x,y) make_pair(x,y)
#define mem(a,val) memset(a,val,sizeof(a))
#define pb push_back
#define f first
#define s second
#define pi 3.141592653589793238
using namespace std;

ll gcd( ll a, ll b )
{
	if(b==0)
	{
		return a;
	}
	else
	{
		return gcd( b, a%b );
	}
}
ll lcm (ll a, ll b)
{
	return (a*b)/gcd(a,b);
}

ll power(ll a, ll b)	//a is base, b is exponent
{
	if(b==0)
		return 1;
	if(b==1)
		return a;
	if(b%2 == 1)
		return (power(a,b-1)*a)%mod;
	ll q = power(a,b/2);
	return (q*q)%mod;
}

int main()
{
	std::ios::sync_with_stdio(false);
	char a,b,c,d;
	cin >> a >> b >> c >> d;

	if((a=='1'||b=='1'||c=='1'||d=='1')&&(a=='9'||b=='9'||c=='9'||d=='9')&&(a=='7'||b=='7'||c=='7'||d=='7')&&(a=='4'||b=='4'||c=='4'||d=='4'))	
		cout << "YES\n";
	else cout << "NO\n";


	return 0;
}


//Hello, this is a snippet.


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

int main() {
  string s;
  cin >> s;
  vector<int> result(s.length(), 0);
  vector<int> p(s.length(), 1);
  int i;
  // for (i = 0; i < p.size(); i++) {
  //   cout << p[i] << ' ';
  // }
  // cout << endl;
  for (i = 0; i < s.length() - 1; i++) {
    if (s.at(i) == 'R' && s.at(i + 1) == 'R') {
      p[i + 2] += p[i];
      p[i] = 0;
    }
    // for (int j = 0; j < p.size(); j++) {
    //   cout << p[j] << ' ';
    // }
    // cout << endl;
  }
  // for (i = 0; i < p.size(); i++) {
  //   cout << p[i] << ' ';
  // }
  // cout << endl;
  for (i = s.length() - 1; i > 0; i--) {
    if (s.at(i) == 'L' && s.at(i - 1) == 'L')  {
      p[i - 2] += p[i];
      p[i] = 0;
    }
  }
  for (i = 0; i < p.size(); i++) {
    cout << p[i] << ' ';
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define per(i,n) for (int i = (n)-1; i >=0; --i)
using namespace std;
using ll = long long;
using vi = vector<int>;
using vv = vector<vi>;

int main(){
    int n;cin>>n;
    vi t(n),x(n),y(n);
    rep(i,n){
        cin>>t[i]>>x[i]>>y[i];
    }
    
    int dx,dt;
    
    rep(i,n){
        
        if(!i){
            dx = abs(x[i]) + abs(y[i]);
            dt = t[i];
        }else{
            dx = abs(x[i]-x[i-1]) + abs(y[i]-y[i-1]);
            dt = t[i]-t[i-1];
        }
        
        if((dx+dt)%2){
            cout << "No" << endl;
            return 0;
        }
        if(dx>dt){
            cout << "No" << endl;
            return 0;
        }
    }
    
    cout << "Yes" << endl;
    
    return 0;
}

Measured memory_bytes: 1408
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<queue>
#include<climits>
#include<set>
#define ll long long
using namespace std;
int main() {
	ll n,count=0;
	cin >> n;
	for (ll i = 1; i <= n; i++) {
		string s = to_string(i);
		if (s.size() % 2 != 0) {
			count++;
		}

	}
	cout << count << endl;
}

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

typedef long long ll;

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> vec(n);

    for (int i = 0; i < n; i++) cin >> vec[i];

    ll right = vec[n - 1]; // 一番右
    ll left = vec[0]; // 一番左
    int roffset = 1;
    int loffset = 1;
    while(roffset + loffset < n){
        if(right > left){
            left += vec[loffset];
            loffset++;
        }else{
            right += vec[n - 1 - roffset];
            roffset++;
        }
    }

    cout << abs(right - left) << endl;

    return 0;
}


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

using namespace std;

int main() {
    int a = 0, b = 0;
    cin >> a >> b;

    if (a == b) {
        cout << "Draw" << endl;
    } else if (b == 1) {
        cout << "Bob" << endl;
    } else if (a == 1) {
        cout << "Alice" << endl;
    } else {
        if (a > b) {
            cout << "Alice" << endl;
        } else {
            cout << "Bob" << endl;
        }
    }

}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
#define rep(i,n) for(long long i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const long long LINF=8931145141919364364,LMOD=998244353;
// const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};

int main(){
    long long n; cin>>n;
    pair<long long,pair<long long,long long>> data[n];
    rep(i,n){
        long long x,y,h; cin>>x>>y>>h;
        data[i]={h,{x,y}};
    }
    sort(data,data+n); reverse(data,data+n);
    rep(cx,101){
        rep(cy,101){
            // cout<<cx<<" "<<cy<<endl;
            bool flg=1;
            long long tmp=-1;
            rep(i,n){
                long long x=data[i].second.first,y=data[i].second.second,h=data[i].first;
                long long H=h+abs(x-cx)+abs(y-cy);
                if(h==0){
                    if(tmp<=abs(x-cx)+abs(y-cy)) continue;
                    else flg=0;
                }
                if(tmp==-1) tmp=H;
                if(H>0){
                    if(tmp!=H){
                        flg=0;
                    }
                }else{
                    flg=0;
                }
            }
            if(flg){
                cout<<cx<<" "<<cy<<" "<<tmp<<endl;
                return 0;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse4")
 
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
 
#define SZ(a) (int)((a).size())
#define ALL(a) a.begin(), a.end()
 
typedef long long LL;
typedef pair<int, int> PII;

const LL LINF = 1e18;
const int LOG = 19;
const int MAX = 200007;

int x[MAX];
LL a[MAX];
vector<pair<int, int> > g[MAX];
vector<pair<LL, int> > s[MAX];
int ptr[MAX];
pair<int, LL> cntr[MAX][LOG];
int szCntr[MAX];
bool U[MAX];
int sz[MAX];
bool took[MAX];

void dfsSz(int v, int p)
{
	sz[v] = 1;
	for(auto to: g[v])
	{
		if(to.first != p && !U[to.first])
		{
			dfsSz(to.first, v);
			sz[v] += sz[to.first];
		}
	}
}

void dfsPB(int v, int p, int u, LL dist)
{
	cntr[v][szCntr[v]++] = {u, dist};
	s[u].push_back({dist + x[v], v});
	for(auto [to, w]: g[v])
		if(to != p && !U[to])
			dfsPB(to, v, u, dist + w);
}

void go(int v)
{
	dfsSz(v, -1);
	int p = -1, totSz = sz[v];
	bool ok = false;
	while(!ok)
	{
		ok = true;
		for(auto to: g[v])
			if(to.first != p && !U[to.first] && 2 * sz[to.first] > totSz)
			{
				p = v;
				v = to.first;
				ok = false;
				break;
			}
		
	}
	s[v].reserve(totSz);
	dfsPB(v, -1, v, 0);
	U[v] = true;
	for(auto to: g[v])
		if(!U[to.first])
			go(to.first);
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	FOR(i, 0, n)
	{
		cin >> x[i];
		a[i] = LINF;
	}
	FOR(i, 0, n - 1)
	{
		int u, v, w;
		cin >> u >> v >> w;
		u--;
		v--;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	go(0);
	priority_queue<pair<LL, int> > gs;
	FOR(i, 0, n)
	{
		sort(ALL(s[i]));
		gs.push({-(a[i] + s[i].begin()->first), s[i].begin()->second});
	}
	LL ans = 0;
	FOR(i, 0, n)
	{
		int v;
		LL w;
		do
		{
			w = -gs.top().first;
			v = gs.top().second;
			gs.pop();
		} while(took[v]);
		took[v] = true;
		if(i)
			ans += w;
		FOR(j, 0, szCntr[v])
		{
			int u = cntr[v][j].first;
			LL d = cntr[v][j].second;
			while(ptr[u] < SZ(s[u]) && took[s[u][ptr[u]].second])
				ptr[u]++;
			a[u] = min(a[u], d + x[v]);
			if(ptr[u] < SZ(s[u]))
			{
				gs.push({-(a[u] + s[u][ptr[u]].first), s[u][ptr[u]].second});
			}
		}
	}
	cout << ans << "\n";
	return 0;
}


Measured memory_bytes: 219800
n, m = (int(i) for i in input().split()) 
a = [int(input()) for i in range(m)] 
is_broken = [1] * n
dp = [0] * (n + 1)
dp[0] = 1
mod = 1000000007
for i in a:
  is_broken[i] = 0

for i in range(n):
  if i >= 1:
    dp[i+1] = dp[i] * is_broken[i] + dp[i-1] * is_broken[i-1]
  else:
    dp[i+1] = dp[i] * is_broken[i]
print(dp[n]%mod)


Measured memory_bytes: 466164
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    x,y,a,b,c = LI()
    p = sorted(LI()) + [inf]
    q = sorted(LI()) + [inf]
    r = [-1] + sorted(LI())
    pi = a - x
    qi = b - y
    ri = c
    while True:
        if p[pi] < q[qi]:
            if p[pi] >= r[ri]:
                break
            pi += 1
            ri -= 1
        else:
            if q[qi] >= r[ri]:
                break
            qi += 1
            ri -= 1

    return sum(p[pi:-1] + q[qi:-1] + r[ri+1:])

print(main())





Measured memory_bytes: 25592
S = str(input())
alp = "abcdefghijklmnopqrstuvwxyz"
s = len(S)
for i in range(s):
  alp = alp.replace(S[i],'')
if alp != '':
  print(S+alp[0])
  exit()
else:
  if S == "zyxwvutsrqponmlkjihgfedcba":
    S = "-1"
  else:
    for j in range(s-1,0,-1):
      if S[j] > S[j-1]:
        alp = list(S[j-1:])
        alp = sorted(alp)
        for k in range(len(alp)+1):
          if alp[k] == S[j-1]:
            S = S[:j-1]+alp[k+1]
            print(S)
            exit()
print(S)

Measured memory_bytes: 3064
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0;i < (int)(n);i++)
using ll = long long;
const ll MOD=1000000007;
const long long INF = 1LL << 60;
const double pi=acos(-1.0);

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



int main()
{
  ll N,K; cin>>N>>K;
  vector<ll> list(100001,0);
  rep(i,N){
    ll a,b; cin>>a>>b;
    list.at(a)+=b;
  }
  
  ll sum=0;
  rep(i,100001){
    sum+=list.at(i);
    if(sum>=K) {cout<<i<<endl; return 0;}
  }
  return 0;
}


Measured memory_bytes: 4032
#!/usr/bin/env python3
#ABC138 B

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
x = 1
for i in range(n):
    x *= a[i]
s = []
for i in range(n):
    s.append(x//a[i])
print(x/sum(s))


Measured memory_bytes: 38384
### global variables

$cmap = {}

### subroutines

def neighbors(nd)
  len = nd.length

  nbrs = []
  c0 = nd[0]

  for i in (1...len)
    c1 = nd[i]
    c01 = c0 + c1

    if ! $cmap[c01].nil?
      nd0 = nd.clone
      nd0[i - 1, 2] = $cmap[c01]
      nbrs << nd0
    end
    c0 = c1
  end

  nbrs
end

### main

for c0 in ['r', 'g', 'b']
  for c1 in ['r', 'g', 'b']
    if c0 != c1
      $cmap[c0 + c1] =
        (c0 != 'r' && c1 != 'r') ? 'rr' :
        (c0 != 'g' && c1 != 'g') ? 'gg' : 'bb'
    end
  end
end

while true
  st = gets.strip
  break if st == '0'

  queue = [st]
  dists = {}
  dists[st] = 0
  dist = 'NA'

  nst = st.length
  ens = ['r' * nst, 'g' * nst, 'b' * nst]

  while ! queue.empty?
    nd = queue.shift

    if ens.include? nd
      dist = dists[nd]
      found = true
      break
    end

    for nd0 in neighbors(nd)
      if dists[nd0].nil?
        dists[nd0] = dists[nd] + 1
        queue << nd0
      end
    end
  end

  puts dist
end

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

using namespace std;

int h[100005];
int is_obs_good[100005];

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> h[i];
		is_obs_good[i] = true;
	}
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		if (h[a] <= h[b])
			is_obs_good[a] = false;
		if (h[b] <= h[a])
			is_obs_good[b] = false;
	}
	int good_obs_count = 0;
	for (int i = 0; i < n; i++) {
		if (is_obs_good[i]) good_obs_count++;
	}
	cout << good_obs_count << "\n";
	return 0;
}


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

int N, x, y, t, dt, dx, dy, oldx=0, oldy=0, oldt=0;

bool valid = true;
int main () {
	cin >> N;
	for(int i=1; i<=N; i++) {
		cin >> t >> x >> y;
		dt = t - oldt;
		dx = abs(x - oldx);
		dy = abs(y - oldy);
		if (dt>=dx+dy && (dt-dx-dy)%2==0) {
			oldt = t;
			oldx = x;
			oldy = y;
		} else {
			valid = false;
			break;
		}
	}
	if (valid) cout << "Yes" << endl;
	else cout << "No" << endl;
}


Measured memory_bytes: 3628
import bisect
import math
N = int(input())
A = list(map(int, input().split()))
A.sort()
already = set()
key = {}

def is_in(t, n):
    i = key.setdefault(t, bisect.bisect_left(A, t))
    if i >= n:
        return -1

    while i < n and t == A[i]:
        if i not in already:
            already.add(i)
            key[t] = i
            return i
        i += 1

    return -1

res = 0
for n in range(len(A) - 1, -1, -1):
    if n in already:
        continue

    a = A[n]
    t = 1 << (int(math.log2(a)) + 1)

    while t > a:
        i = is_in(t - a, n)
        if i != -1:
            res += 1
            break
        t >>= 1

print(res)
print("")


Measured memory_bytes: 43728
//
// Created by kuroneko on 2019-08-10.
//

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

typedef long long ll;

#define INF 1000000000000009LL
#define MOD 1000000007LL

typedef int Weight;
struct Edge {
    int src, dst;
    Weight weight;
    Edge(int src, int dst, Weight weight):src(src), dst(dst), weight(weight) {}
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

typedef vector<Weight> Array;
typedef vector<Array> Matrix;

int main() {
    int K, X; cin >> K >> X;

    for (int i = X - K + 1; i < X + K; i++) {
        cout << i;
        if (i != X + K - 1) cout << " ";
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 888
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(n); ++i)
#define repr(i, a, b) for (int i=a; i<(b); ++i)
#define reprev(i, n) for (int i=n-1; i>=0; --i)
#define reprrev(i, a, b) for (int i=b-1; i>=(a); --i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

const int MAX_N = 15;

int n;
int d[MAX_N][MAX_N];
// 既に通った集合がSで、現在場所がvのとき、まだ通っていない全てを巡って、0に到達するときの最小コストがdp(S)(v)
int dp[1<<MAX_N][MAX_N];

const ll INF = 100100100100100100;
const int iINF = 1000000000;

int dfs(int S, int v) {
    // cout << S << " " << v << endl;
    
    if (dp[S][v] >= 0) {
        return dp[S][v];
    }
    if (S == (1 << n) - 1 && v == 0) {
        return dp[S][v] = 0;
    }

    int res = iINF;
    rep(u, n) {
        if (!(S >> u & 1) && d[v][u] != -1) {
            // Sのu桁目が集合になければ
            res = min(res, dfs(S | 1 << u, u) + d[v][u]);
            // Sのu桁目に1を立てて、場所はu + vからuへの距離
        }
    }
    return dp[S][v] = res;
}

int main() {
    cout << fixed << setprecision(10);

    cin >> n;
    int ne; cin >> ne;

    // memset(dp, -1, sizeof(dp));
    // memset(d, iINF, sizeof(d));
    rep(i, MAX_N) {
        rep(j, MAX_N) {
            d[i][j] = -1;
        }
    }
    rep(i, 1 << MAX_N) {
        rep(j, MAX_N) {
            dp[i][j] = -1;
        }
    }

    rep(i, ne) {
        int f, t, v; cin >> f >> t >> v;
        d[f][t] = v;
    }
    /*
    rep(i, n) {
        rep(j, n) {
            cout << d[i][j] << " ";
        }
        cout << endl;
    }
    */
    int ans = dfs(0, 0);
    if (ans == iINF) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }
    return 0;
}


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

int main(){
    int n, y; cin >> n >> y;
    int res1 = -1, res2 = -1, res3 = -1;
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n - i; j++){
            int k = n - i - j;
            int total = 10000 * i + 5000 * j + 1000 * k;
            if(total == y){
                res1 = i;
                res2 = j;
                res3 = k;
            }
        }
    }
    cout << res1 << " " << res2 << " " << res3;
}

Measured memory_bytes: 256
#!/usr/bin/env python
"""AtCoder Beginner Contest 168: B - ... (Triple Dots)
https://atcoder.jp/contests/abc168/tasks/abc168_b
"""


def main():
    K = int(input())
    S = input()

    if len(S) <= K:
        print(S)
    else:
        print("{}...".format(S[0:K]))


if __name__ == '__main__':
    main()


Measured memory_bytes: 9028
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())
n = 0
if e-a > k or e-b > k or d-a > k or e-c > k or d-b > k or c-a > k or e-d > k or d-c > k or c-b > k or b-a > k:
    n = 1

if n == 1:
    print(":(")
if n == 0:
    print("Yay!")

Measured memory_bytes: 3064
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace AtCoder
{
    class Program
    {
        private static string Read() { return Console.ReadLine(); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }

        static int[] Solve(int N, Tuple<string, int, int>[] restaurants)
        {
            return restaurants.OrderBy(r => r.Item1).ThenByDescending(r => r.Item2).Select(r => r.Item3).ToArray();
        }

        static void Main(string[] args)
        {
            int N = ReadInt();
            var restaurants = new Tuple<string, int, int>[N];
            for (int i = 0; i < N; ++i)
            {
                var V = Read().Split();
                restaurants[i] = new Tuple<string, int, int>(V[0], int.Parse(V[1]), i + 1);
            }
            var ans = Solve(N, restaurants);
            foreach (int n in ans) { Console.WriteLine(n); }
        }
    }
}


Measured memory_bytes: 13664
def i():
	return int(input())
def i2():
	return map(int,input().split())
def s():
	return str(input())
def l():
	return list(input())
def intl():
	return list(int(k) for k in input().split())

n = i()
s = s()
cnt = 0
ans = 0

for i in range(n):
	if s[i] == "I":
		cnt += 1
	else:
		cnt -= 1
	if cnt >= ans:
		ans = cnt
print(ans)

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


void solve(long long A, long long B, long long C, long long D){
    cout << max(A*B, C*D) << endl;
}

int main(){
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    long long C;
    scanf("%lld",&C);
    long long D;
    scanf("%lld",&D);
    solve(A, B, C, D);
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define X first
#define Y second
#define mod 1e9+7
#define pb push_back
#define mp make_pair
#define abs(x) ((x)>0?(x):(-(x)))
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define memres(a) memset(a,0,sizeof(a))
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	char a[100];
	cin>>a;
	int l=strlen(a),cnt=0;
	for(int i=0;i<l-i-1;i++){
		if(a[i]!=a[l-i-1])cnt++;
	}
	cout<<cnt<<endl;
return 0;
}


Measured memory_bytes: 256
import sys

def solve():
    L = raw_input()
    data = []
    data.append(L.count("K"))
    data.append(L.count("U"))
    data.append(L.count("P"))
    data.append(L.count("C"))

    print min(data)
    
                            
if __name__ == "__main__":
    solve()
   

Measured memory_bytes: 4216
#include <iostream>
#include <algorithm>
using namespace std;
int main(void) {
  int p[3];
  int j[2];

  while(cin >> p[0] >> p[1] >> p[2] >> j[0] >> j[1]) {
    sort(p, p+3);
    sort(j, j+2);
    int ans = p[0] + j[0];
    cout << ans - 50 << endl;
  }
  return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define REP(i, n) for(int i=0; i<n; i++)
#define FOR(i, s, n) for(int i=s; i<n; i++)

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> mat;

int main(){
    int D, N;
    cin >> D >> N;
    int ans;
    if (N == 100){
        ans = pow(100, D) * (N+1);
    }else{
        ans = pow(100, D) * N;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<algorithm>
#include<string>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<utility>
#include<functional>
#include<cassert>

using namespace std;
typedef pair<int, int> P;
typedef long long int ll;

int main(void) {
	int n, ans = 0;
	cin >> n;
	vector<int> l(n);
	for (int i = 0; i < n; i++) {
		cin >> l[i];
	}
	sort(l.begin(), l.end());
	for (int i = 0; i < n-2; i++) {
		for (int j = i + 1; j < n - 1; j++) {
			for (int k = j + 1; k < n; k++) {
				if (l[i] + l[j] > l[k]) {
					ans++;
				}
				else {
					j++;
					k = j;
				}
			}
		}
	}
	cout << ans<<endl;
}

Measured memory_bytes: 384
readlines.each do |l|
  a,b,c,d,e = l.split(",").map(&:to_i).sort
  kinds = [a,b,c,d,e].uniq.size
  if a==d || b==e
    puts "four card"
  elsif kinds==2
    puts "full house"
  elsif kinds==5 && (e-a==4 || a==1 && e==13 && e-b==3)
    puts "straight"
  elsif a==c || b==d || c==e
    puts "three card"
  elsif kinds==3
    puts "two pair"
  elsif kinds==4
    puts "one pair"
  else
    puts "null"
  end
end

Measured memory_bytes: 6112
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define pb push_back
#define fi first
#define se second
const int maxn=1e6+10;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
ll prime[maxn];
void init()
{
	for(int i=2;i<maxn;i++)
	{
		if(!prime[i]) prime[++prime[0]]=i;
		for(int j=1;j<=prime[0]&&prime[j]<maxn/i;j++)
		{
			prime[i*prime[j]]=1;
			if(i%prime[j]==0) break;
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	init();
	ll a,b;
	cin>>a>>b;
	vector<ll> fa,fb;
	for(int i=1;i<=prime[0]&&prime[i]*prime[i]<=a;i++)
	{
		if(a%prime[i]==0)
		{
			fa.pb(prime[i]);
			while(a%prime[i]==0) a/=prime[i];
		}
	}
	if(a!=1) fa.pb(a);
	for(int i=1;i<=prime[0]&&prime[i]*prime[i]<=b;i++)
	{
		if(b%prime[i]==0)
		{
			fb.pb(prime[i]);
			while(b%prime[i]==0) b/=prime[i];
		}
	}
	if(b!=1) fb.pb(b);
	int ans=0;
	for(auto x: fa) for(auto y: fb) if(x==y) ans++;
	cout<<ans+1<<'\n';
    return 0;
}



Measured memory_bytes: 8064
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n,k;
    cin >> n >> k;
    int a[n];
    for(int i=0;i<n;i++) cin >> a[i];
    for(int i=0;i<n-k;i++){
        if(a[i]<a[k+i]) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}

Measured memory_bytes: 4400
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, M; cin >> N >> M;
  cout << (1900 * M + 100 * (N - M)) * pow(2, M) << endl;
  return 0;
}

Measured memory_bytes: 256
# ABC154 C
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
n=int(input())
a=nl()
d=set(a)

if len(d)==n:
    print('YES')
elif len(d)<n:
    print('NO')

Measured memory_bytes: 25932
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    K = int(input())
    X = int(input())
    Y = int(input())

    ans = 0
    for i in range(1, N+1):
        if i <= K:
            ans += X
        else:
            ans += Y
    print(ans)

if __name__ == "__main__":
    main()

Measured memory_bytes: 3060
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
const ll INF = 1e+14;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second

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

  ll K, A, B; cin >> K >> A >> B;
  ll ans = 1;
  if(B <= A + 2) cout << K + 1 << "\n";
  else {
      if(K + 1 < A) cout << K + 1 << "\n";
      else {
          K -= A - 1;
          ans += A - 1;
          ans += (B - A) * (K / 2) + (K%2 == 1 ? 1 : 0);
          cout << ans << "\n";
      }
  }
  return 0;
}

Measured memory_bytes: 256
//============================================================================
// Name        : JOI.cpp
// Author      :2015 ho3
// Version     :???11:08
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include<algorithm>
#include <queue>
using namespace std;

int N,Q;
long long X[200001]={};
int D[200001]={};
int L[200001]={};
const int INF=1000000001;
long long BX[300002];
long long BY[300002];
int N_MAX=18;

long long outBY(int n1){
	long long ans=0;
	int ps=0;
	for(int i=(1<<N_MAX);i>0;i=(i>>1)){
		if(n1>=i){
			ans+=BY[i+ps];
			n1-=i;
			ps+=i;
			if(n1==0)break;
		}
	}
	return ans;
}
long long outBX(int n1){
	long long ans=0;
	int ps=0;
	for(int i=(1<<N_MAX);i>0;i=(i>>1)){
		if(n1>=i){
			ans+=BX[i+ps];
			n1-=i;
			ps+=i;
			if(n1==0)break;
		}
	}
	return ans;

}
int inBX(int n1,int p){
	int ps=0;
	for(int i=(1<<N_MAX);i>0;i=(i>>1)){
		if(n1<=i)BX[i+ps]+=(long long)p;
		if(n1>=i){
			n1-=i;
			ps+=i;
			if(n1==0)break;
		}
	}
	return 0;
}
int inBY(int n1,int p){
	int flg=0;
	for(int i=1;i<1<<(N_MAX+1);i=i<<1){
		if((n1&i)==i){
			if(flg==0){
				flg=1;
				BY[n1]+=(long long)p;
			}
			n1-=i;
		}else if(flg==1){
			BY[n1+i]+=(long long)p;
		}
	}
	return 0;
}

int initBX(){
	for(int i=1;i<N+1;++i)inBX(i,1);
	return 0;
}
int searchD1(long long x1){
	if(BX[1]+BY[1]>x1)return 0;
	if(BX[1<<N_MAX]+BY[1<<N_MAX]<x1)return N+1;
	int bs=0;
	for(int i=1<<(N_MAX-1);i>0;i=i>>1){
		if(BX[bs+i]+BY[bs+i]<=x1){
			x1-=(BX[bs+i]+BY[bs+i]);
			bs+=i;
		}
	}
	return bs;
}
int searchD2(long long x1){
	if(BX[1]-BY[1]>x1)return 0;
	if(BX[1<<N_MAX]-BY[1<<N_MAX]<x1)return N+1;
	int bs=0;
	for(int i=(1<<(N_MAX-1));i>0;i=(i>>1)){
		if(BX[bs+i]-BY[bs+i]<=x1){
			x1-=(BX[bs+i]-BY[bs+i]);
			bs+=i;
		}
	}
	return bs;
}



int main() {
	cin>>N>>Q;

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

	initBX();

	int pos=0;
	for(int i=Q-1;i>-1;--i){
		if(D[i]==1){
			pos=searchD1(X[i]);
			if(pos>0){
				inBX(1,-L[i]);
				inBY(1,L[i]);
				if(pos<N){
					inBX(pos+1,L[i]);
					inBY(pos+1,-L[i]);
				}
			}
		}else{
			pos=searchD2(X[i]);
			if(pos<N){
				inBX(pos+1,L[i]);
				inBY(pos+1,L[i]);
			}
		}
	}
	for(int i=1;i<N+1;++i){
		cout<<outBY(i)<<endl;
	}



	return 0;
}

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

// dpを使った場合
// こいつら↓をmainの外に出し、かつCの配列なら行けた

string options[4] = {"dream", "dreamer", "erase", "eraser"};
bool dp[100010];

int main() {
  string s;
  cin >> s;
  
  dp[0] = 1;
  for (int i = 0; i < s.size(); i++) {
    if (!dp[i]) continue;
    for (string c : options) {
      // sのi番目からc.size要素までがoptionsのどれかと一致したら、
      // その末尾の添字に対応するdpの位置をtrueにする
      if (s.substr(i, c.size()) == c) dp[i + c.size()] = 1;
    }
  }
  
  // dp[s.size()](つまりsの末尾)がtrueということは、sがoptionsで綺麗に分割できたということ
  cout << (dp[s.size()] ? "YES" : "NO") << endl;
}


Measured memory_bytes: 3808
#include<bits/stdc++.h>
#define MOD 1000000007
#define F first
#define S second

typedef long long ll;
using namespace std;

int main()
{
    string s, t;
    cin >> s >> t;
    s += s;
    cout << (s.find(t) != std::string::npos ? "Yes" : "No");
    return 0;
}


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

int main(void){
    int n;
    cin >> n;
    double sum =0;
    rep(i,n){
        int a;
        cin >> a;
        sum+=1.0/a;
    }
    double ans=1/sum;
    printf("%.10f", ans);

    return 0;
}

Measured memory_bytes: 256
using System;

public class hello
{
    public static void Main()
    {
        string line;
        for (; (line = Console.ReadLine()) != null;)
        {
            string[] s = line.Trim().Split(' ');
            var a = int.Parse(s[0]);
            var b = int.Parse(s[1]);
            var c = int.Parse(s[2]);
            var count = 0;
            for (int i = 1; i <= 10; i++)
            {
                if (i == a | i == b | i == c) goto next;
                if (a + b + i <= 20) count++;
                next:;
            }
            if (count >= 4) Console.WriteLine("YES");
            else Console.WriteLine("NO");
        }
    }
}

Measured memory_bytes: 8672
/******************************************
* AUTHOR : HRITIK AGGARWAL *
******************************************/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100005
#define MOD 1000000007
#define dd double
#define vi vector<int>
#define vll vector<ll>
#define forr(i, n) for(int i = 0; i < n; i++)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep1(i,b) for(int i=1;i<=b;i++)
#define pb push_back
#define mp make_pair
#define clr(x) x.clear()
#define sz(x) ((int)(x).size())
#define ms(s, n) memset(s, n, sizeof(s))
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define int ll
ll po(ll a, ll x,ll m){ if(x==0){return 1;}ll ans=1;ll k=1;  while(k<=x) {if(x&k){ans=((ans*a)%m);} k<<=1; a*=a; a%=m; }return ans; }
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
   
    int n,k;
    cin>>n>>k;
    int ans = 0;
    while(n>0){
        ans++;
        n/=k;
    }   
    cout<<ans<<"\n";
return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)n; i++)
#define all(x) (x).begin(),(x).end()
typedef long long int ll;
using namespace std;
int main()
{
  int n;
  string s;
  cin >> n>>s;
  int size = s.size();
  vector<bool > first(10, false);
  vector<bool > second(10, false);
  vector<bool > third(10, false);

  int numf, nums, numt;
  numf = nums = numt = 0;
  int ans = 0;
  REP(i, size){
    int f = s[i] - '0';
    nums = numt = 0;
    REP(j,10) second[j] = false;
    if(!first[f]){
      first[f] = true;
      numf ++;
      for(int j = i + 1; j < size;j++){
	int sec = s[j] - '0';
	if(!second[sec]){
	  second[sec] = true;
	  nums ++;
	  numt = 0;
	  REP(k,10) third[k] = false;
	  for(int k = j +1;k < size;k++){
	    int t = s[k] - '0';
	    if(!third[t]){
	      third[t] = true;
	      numt ++;
	      ans ++;
	    }
	    if(numt == 10){
	      break;
	    }
	  }
	}
	if(nums == 10){
	  break;
	}
      }
    }
    if(numf == 10){
      break;
    }
  }
  cout << ans <<endl;
}


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

int main(void)
{
	int n;
	int i;
	double x;
	double y;
	double ang;
	
	while (scanf("%d", &n), n != -1){
		x = 1.0;
		y = 0.0;
		ang = 180.0;
	
		for (i = 1; i < n; i++){
			ang -= 90.0;
			
			if (ang < -180.0){
				ang += 360.0;
			}
			
			ang *= M_PI / 180;
			
			y += sin(ang);
			x += cos(ang);
			
			ang = atan2(y, x) * 180 / M_PI - 180;
			
			if (ang < -180){
				ang += 360;
			}
		}
		
		printf("%.2f\n%.2f\n", x, y);
	}
	
	return (0);
}

Measured memory_bytes: 728