akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef complex<double> P;
static const double EPS = 1e-8;
static const int INF = (int)1e8;

#define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i)
#define REP(i,n) for (int i=0; i<(int)(n); ++i)
#define FOREQ(i,k,n) for (int i=(k); i<=(int)(n); ++i)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define FIND(m,w) ((m).find(w)!=(m).end())
int ror,mas,eve;
int N[50];
int E[50];
int A[50];
int V[4];
double memo[50][5000];
double solve(int go, int money){
  REP(i,eve){
    if(N[i]==go){
      if(E[i]==1){
        go += A[i];
      }
      if(E[i]==2){
        money += A[i];
      }
      if(E[i]==3){
        money -= A[i];
        if(money<0)money = 0;
      }
      break;
    }
  }
  if(go>=mas) return money;
  if(money<5000){
    if(memo[go][money]!=-1){
      return memo[go][money];
    }
  }else if(money>5000){
    abort();
  }
  double ret = 0;
  REP(i,ror){
    ret += solve(go+V[i], money)/ror;
  }
  return memo[go][money] = ret;
}

int main(void){
  while(cin>>ror>>mas>>eve,ror||mas||eve){
    //memset(memo,0,sizeof(memo));
    REP(i,50)REP(j,5000)memo[i][j] = -1;
    REP(i,ror)cin>>V[i];
    REP(i,eve){
      cin>>N[i]>>E[i]>>A[i];
    }
    cout<<(int)(solve(0,0)+EPS)<<endl;
  }
  return 0;
}

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

int main(){
  int n;
  ll sum=0;
  cin >> n;
  rep(i, n){
    if((i+1)%3==0||(i+1)%5==0){
      continue;
    }
    else{
      sum+=i+1;
    }
  }

  cout << sum << endl;

  return 0;
}

Measured memory_bytes: 3560
my $p = <STDIN>;
my $q = <STDIN>;
chomp($p);
chomp($q);
my (@a, @b);
my ($ans1,$ans2);
my $r= 10000;

for(0..$p-1){
    @a = split / /, $q;
    @b = splice(@a,$_);

    ($ans1,$ans2) = (0, 0);

    $ans1 += $_ foreach @a;
    $ans2 += $_ foreach @b;
    $r = $ans1-$ans2 if ($ans1>$ans2 && $r > $ans1-$ans2);
    $r = $ans2-$ans1 if ($ans1<=$ans2 && $r > $ans2-$ans1);
}

print $r."\n";

1;


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

const int MAX_N = 100000;
int N;
std::vector<int> ab[MAX_N];
int distance[2][MAX_N];
bool visit[2][MAX_N];

void dfs(int index, int x, int d){
   if(visit[index][x]) return;
   visit[index][x] = true;
   distance[index][x] = d;

   for(int i=0; i<ab[x].size(); ++i){
      dfs(index,ab[x][i],d+1);
   }

   return;
}

int main(){
   std::cin >> N;
   int a, b;
   for(int i=0; i<N-1; ++i){
      std::cin >> a >> b;
      --a; --b;
      ab[a].push_back(b);
      ab[b].push_back(a);
   }

   dfs(0,0,0);
   dfs(1,N-1,0);
   
   int n[2] = {0,0};
   for(int i=0; i<N; ++i){
      if(distance[0][i]<=distance[1][i]) ++n[0];
      else ++n[1];
   }
   if(n[0]>n[1]) std::cout << "Fennec" << std::endl;
   else std::cout << "Snuke" << std::endl;
   return 0;
}


Measured memory_bytes: 11392
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		//List<String> list= new ArrayList<String>(Arrays.asList(s.split("")));
		//List<Integer> list=new ArrayList<Integer>();
		//Integer[] array = new Integer[m];
		int x = sc.nextInt();
		int ama = x%100;
		Integer[] array = new Integer[6];
		for(int i=0;6>i;i++) {
			array[i]=0;
		}
		while(true) {
			if(ama==0)
				break;
			if(ama-5>=0) {
				array[5]=array[5]+1;
				ama=ama-5;
			}
			else if(ama-4>=0) {
				array[4]=array[4]+1;
				ama=ama-4;
			}
			else if(ama-3>=0) {
				array[3]=array[3]+1;
				ama=ama-3;
			}
			else if(ama-2>=0) {
				array[2]=array[2]+1;
				ama=ama-2;
			}
			else if(ama-1>=0) {
				array[1] = array[1]+1;
				ama=ama-1;
			}
			//System.out.println(ama);
		}
		int count=0;
		for(int i=0;6>i;i++) {
			if(i==1)
				count=count+101*array[i];
			else if(i==2)
				count=count+102*array[i];
			else if(i==3)
				count=count+103*array[i];
			else if(i==4)
				count=count+104*array[i];
			else if(i==5)
				count=count+105*array[i];
		}
		if(count+100<=x)
			System.out.println("1");
		else if(count==x)
			System.out.println("1");
		else
			System.out.println("0");
	}
}

Measured memory_bytes: 23124
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int happiness[n][3];

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<3;j++)
        {
            cin>>happiness[i][j];
        }
    }

    int dp[n][3];
    for(int i=0;i<3;i++)dp[0][i] = happiness[0][i];

    for(int i=1;i<n;i++)
    {
        for(int j=0;j<3;j++)
        {
            dp[i][j] = happiness[i][j] + max({ dp[i-1][(j+1)%3],dp[i-1][(j+2)%3] });
        }
    }

    int ans = 0;
    for(int i=0;i<3;i++)ans = max(ans,dp[n-1][i]);

    cout<<ans;

}


Measured memory_bytes: 2560
#include<stdio.h>

int card[200];
int k[1000];

void cut(int k, int n) {
	int i, a[200], b[200], j = 0, l = 0;
	for (i = 0; i < k; i++) 
		a[j++] = card[i];
	for (i = k; i < n * 2; i++)
		b[l++] = card[i];
	j = 0;
	for (i = 0; i < 2 * n; i++) {
		if (i < l)card[i] = b[i];
		else card[i] = a[j++];
	}
}

void refle_shuffle(int n) {
	int i,j=0,k=0;
	int a[200], b[200];
	for (i = 0; i < n; i++)a[i] = card[i];
	for (i = n; i < 2 * n; i++)b[j++] = card[i];
	j = 0;
	for (i = 0; i < 2 * n; i++) {
		if (i % 2 == 0)card[i] = a[j++];
		else card[i] = b[k++];
	}
}

int main(void) {
	int n, m,i;
	scanf("%d",&n);
	scanf("%d", &m);

	for (i = 0; i < 2 * n; i++)
		card[i] = i + 1;

	for (i = 0; i < m; i++)
		scanf("%d",&k[i]);
	
	for (i = 0; i < m; i++) {
		if (k[i] == 0) refle_shuffle(n);
		else cut(k[i],n);
	}
	for (i = 0; i < 2*n; i++)printf("%d\n",card[i]);
	return 0;
}

Measured memory_bytes: 604
n,k = map(int,input().split())
h = []
for i in range(n):
    h.append(int(input()))
h.sort()
min_diff = h[k] - h[0]
for i in range(n-k +1):
    h_min = h[i]
    h_max = h[i + k -1]
    if min_diff > h_max - h_min:
        min_diff = h_max - h_min
print(min_diff)

Measured memory_bytes: 7384
#include<cstdio>
#include<iostream>
#include<cmath>
#include<string>

using namespace std;

int n, k, i;
bool d[10] = {false};

bool check(){
    int m = n;
    while(m > 0){
        if(d[m%10] == true) return false;
        m /= 10;
    }
    return true;
}

main(){
    scanf("%d %d", &n, &k);
    while(k > 0){
        scanf("%d", &i);
        d[i] = true;
        k--;
    }
    
    while(!check()) n++;
    cout << n;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int Inf = 2100000010;
constexpr ll INF= 2000000000000000000;
constexpr ll MOD = 1000000007;
const double PI = 3.1415926535897;
typedef pair<int,int> P;
typedef pair<int,P> PP;

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

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

ll mod(ll val, ll M) {
    val = val % M;
    if(val < 0) {
        val += M;
    }
    return val;
}

template<typename T>
T RS(T N, T P, T M){
    if(P == 0) {
        return 1;
    }
    if(P < 0) {
        return 0;
    }
    if(P % 2 == 0){
        ll t = RS(N, P/2, M);
        if(M == -1) return t * t;
        return t * t % M;
    }
    if(M == -1) {
        return N * RS(N,P - 1,M);
    }
    return N * RS(N, P-1, M) % M;
}

int main() {
    int K;
    cin >> K;
    for(int i = 0;i < K;i++) {
        cout << "ACL";
    }
    cout << endl;
}

Measured memory_bytes: 3624
import numpy as np

N = int(input())
B = list(map(int, input().split()))

testA = B + [0]
testB = [0] + B
#print(testA)
#print(testB)
#print((np.array(testA)-np.array(testB))[:len(B)])
temp = (np.array(testA)-np.array(testB))[:len(B)]
#print(temp[temp < 0])
res = sum(temp[temp < 0])
#print(res)
print(B[0] + sum(B) + res)

Measured memory_bytes: 20260
n = int(input())
a = list(map(int,input().split()))
 
mod = 10**9+7
sum_a = sum(a)%mod
sum_a2 = sum_a**2%mod
 
for i in range(n):
    sum_a2 -= (a[i]**2)%mod
    sum_a2 %= mod
    
if sum_a2%2 == 0:
    ans = sum_a2//2
else:
    ans = ((sum_a2+mod)//2)%mod

print(ans)

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

using namespace std;

int main()
{
    int x, y;
    scanf("%d %d", &x, &y);

    if (y % 2 == 1)
        printf("No");
    else if (x * 2 > y)
        printf("No");
    else if (x * 4 < y)
        printf("No");
    else
        printf("Yes");

    return 0;
}

Measured memory_bytes: 3824
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define MOD 1000000007
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
using P = pair<int,int>;

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

int main()
{
  ll N,M;
  cin >> N >> M;
  string S,T;
  cin >> S >> T;

  ll GCD = gcd(N,M);

  int flag = 0;
  REP(i,GCD){
    if(S.at(i*N/GCD)!=T.at(i*M/GCD)){
      flag = 1;
    }
  }

  if(flag ==1){
    cout << -1 << endl;
  }else{
    cout << M*N/GCD << endl;
  }
}

Measured memory_bytes: 512
h,w,k = map(int,input().split())
S = [list(map(int,list(input()))) for _ in range(h)]
ans = 10**9+7
for i in range(1 << (h-1)):
    group = [[0]*w]
    g_id = 0
    group[g_id] = [s+b for s, b in zip(S[0], group[0])]
    for j in range(1, h):
        if (i>>(j-1))&1:
            group.append([0]*w)
            g_id += 1
        group[g_id] = [s+b for s, b in zip(S[j], group[g_id])]
    if not all([all([i <= k for i in b]) for b in group]):
        continue
    cnt = len(group) - 1
    g_cnt = [0] * len(group)
    
    for jj in range(w):
        for g_id in range(len(group)):
            g_cnt[g_id] += group[g_id][jj]
        if any([c > k for c in g_cnt]):
            cnt  += 1
            for g_id in range(len(group)):
                g_cnt[g_id] = group[g_id][jj]
    ans = min(ans, cnt)
print(ans)

Measured memory_bytes: 55644
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long

int32_t main(){
	IOS;
	int n;
	cin >> n;
	vector<bool> pos(1000005, false);
	vector<int> tot(1000005, 0);
	int arr[n];
	for(int i = 0; i < n; i++)
		cin >> arr[i];

	for(int i = 0; i < n; i++){
		int cur = arr[i];
		tot[cur]++;
		if( pos[cur] == false && tot[cur] == 1 ){
			for(int j = 2*cur; j < pos.size(); j+=cur)
				pos[j] = true;
		}
	}

	int cnt = 0;
	for(int i = 0; i < n; i++)
		if( pos[arr[i]] == false && tot[arr[i]] == 1 )
			cnt++;

	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 12700
//include
//------------------------------------------
#include <bits/stdc++.h>
using namespace std;
//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef long long ll;
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const long long INF = 1000000007;
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
// chmax chmin
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 main(void){
    int N; cin >> N;
    int F[N][5][2]; REP(i,N)REP(j,5)REP(k,2) cin >> F[i][j][k];
    int P[N][11]; REP(i,N)REP(j,11) cin >> P[i][j];
    int ans = -(int)INF;
    for(int i=1; i<1024; i++){
        int open[10];
        int bit = 1;
        REP(j,10){
            if(bit & i) open[j] = 1;
            else open[j] = 0;
            bit <<= 1;
        }
        int c[N]; REP(i,N) c[i] = 0;
        REP(i,N){
            REP(j,10){
                if(open[j] && F[i][j/2][j%2]) c[i]++;
            }
        }
        int benefit = 0;
        REP(i,N) benefit += P[i][c[i]];
        chmax(ans, benefit);
    }
    cout << ans << endl;
    return 0;
}

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

#define rep(i,n) for(int (i)=0;(i)<(n);++(i))
#define FOR(i,a,b) for(int (i)=(a);i<(b);++(i))
#define ALL(obj) (obj).begin(),(obj).end()
#define space <<" "<<
using namespace std;



    vector<int> v,w;

int given_dp(int n,int W){
    vector< vector<int> > dp(n+1,vector<int>(W+1));
    rep(i,n+1)dp[i][0]=0;
    rep(i,W+1)dp[0][i]=0;
    FOR(i,1,n+1){
        FOR(j,1,W+1){
            if(j-w[i-1]<0) dp[i][j]= dp[i-1][j];
            else dp[i][j] =max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1]);
        }
    }
    return dp[n][W];
}

int main(){
    int  N,W;
    cin>>N>>W;
    int k;

    for(int i=0;i<N;i++){
    cin>>k;
    v.push_back(k);
    cin>>k;
    w.push_back(k);
    }

    cout<<given_dp(N,W)<<endl;
}






Measured memory_bytes: 6844
h,w=map(int,input().split())
n=int(input())
a=list(map(int,input().split()))
nums=[]
for i in range(n):
    nums+=[(i+1) for x in range(a[i])]
for i in range(h):
    print(*(nums[i*w:i*w+w] if i%2==0 else nums[i*w:i*w+w][::-1]))


Measured memory_bytes: 3828
#include<iostream>
#include<cstdio>

using namespace std;

int main(){
   int a,b,x,i;
   
   while(cin>>a>>b){
      i = 0;
      x = a+b;
      
      for(;;){
         if(x <= 0)
            break;
         
         x = x/10;
         i++;
      }
      printf("%d\n",i);
   }
   return 0;
}

Measured memory_bytes: 0
N, M = map(int, input().split())
A_ = [int(input()) for _ in range(M)]
A = [0] * (N+3)
for a in A_:
    A[a] = 1
dp = [0] * (N+3)
dp[0] = 1

mod = 10**9+7

for i in range(1, N+1):
    if A[i-1] == 0:
        dp[i] += dp[i-1]
    if A[i-2] == 0:
        dp[i] += dp[i-2]
    dp[i] %= mod
print(dp[N])

Measured memory_bytes: 9612
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            int n=sc.nextInt()%39;
            System.out.printf("3C%02d\n",n==0?39:n);;
        }
    }
}


Measured memory_bytes: 25944
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>

using namespace std;
using LLONG = long long;
const LLONG MOD = 1000000007;

int main()
{
    string S; cin >> S;
    string goal = "AKIHABARA";
    // 字数オーバーはNG
    if (S.length() > goal.length())
    {
        cout << "NO\n";
    }
    // 字数一致時は，既に完成しているときのみOK
    else if (S.length() == goal.length())
    {
        cout << (S == "AKIHABARA" ? "YES\n" : "NO\n");
    }
    // 字数が少ないとき
    else
    {
        string added = "";
        int i = 0;
        for (const char ch : goal)
        {
            if (i < S.length())
            {
                if (S[i] == ch)
                {
                    added += ch;
                    ++i;
                }
                else if (ch == 'A')
                {
                    added += 'A';
                }
                else
                {
                    break;
                }
            }
            else
            {
                added += 'A';
            }
        }
        cout << (added == goal ? "YES\n" : "NO\n");
    }
}


Measured memory_bytes: 384
using System;
public class Hello{
    public static void Main(){
        string[] input = Console.ReadLine().Split(' ');
        int A = int.Parse(input[0]);
        int B = int.Parse(input[1]);
        
        if(A % 3 == 0|| B % 3 == 0||(A + B) % 3 == 0){
            Console.WriteLine("Possible");
        }else{
            Console.WriteLine($"Impossible");
        }
    }
}

Measured memory_bytes: 13140
using System;
using System.Linq;

namespace b
{
    class Program
    {
        static void Main(string[] args)
        {
            var _ = Console.ReadLine().Split();
            var n = int.Parse(_[0]);
            var m = int.Parse(_[1]);
            var x = int.Parse(_[2]);
            var y = int.Parse(_[3]);

            var xa = Console.ReadLine().Split().Select(k => int.Parse(k)).ToArray();
            var ya = Console.ReadLine().Split().Select(k => int.Parse(k)).ToArray();

            var xmax = xa.Max();
            var ymin = ya.Min();

            var f = false;
            for(var i = x + 1; i <= y; i++){
                if(i > xmax && i <= ymin){
                    f = true;
                    break;
                }
            }

            Console.WriteLine(f ? "No War" : "War");
        }
    }
}


Measured memory_bytes: 13396
import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long a = sc.nextLong();
        long b = sc.nextLong();
        System.out.println(help(n,a,b));
    }
    static long help(long n, long a, long b){
        if(a>b) return 0;
        if(n==1) return a==b?1:0;
        if(n==2) return 1;
        return (n-2)*(b-a)+1;
    }
}


Measured memory_bytes: 22996
n = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(n):
    A[i] %= (10**9 +7)
s = sum(A)
for i in range(n-1):
    s -= A[i]
    ans += A[i]*s
print(ans%(10**9 + 7))

Measured memory_bytes: 94256
import java.util.*;

public class Main {
    static final int MOD = 1000000007;
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		double w = sc.nextInt();
		double h = sc.nextInt();
		int x = sc.nextInt();
		int y = sc.nextInt();
		int result = 0;
		if (x * 2 == w && y * 2 == h) {
		    result++;
		}
		System.out.println((w * h / 2.0) + " " + result);
   }
}


Measured memory_bytes: 21844
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <fstream>
#include <bitset>
#include <time.h>
#include <tuple>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef complex<double> Point;

#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = (1LL << 60) - 1;
const ll MOD = 1e9 + 7;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,N) for(int i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second
#define N_SIZE (1LL << 20)
#define NIL -1
#define MAX_N 100100 * 3

int a, b, c;

int main() {
	cin >> a >> b >> c;
	if (a <= c&&c <= b)cout << "Yes" << endl;
	else cout << "No" << endl;
}

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

using namespace std;

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

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

  sort(a.rbegin(), a.rend());

  int alice = 0, bob = 0;
  for(int i = 0; i < n; i++) {
    if(i%2 == 0) alice += a[i];
    else bob += a[i];
  }

  cout << alice - bob << endl;
}


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

struct Mixed {
    long long a, b, c;
    static long long Ma, Mb;
    Mixed() : a(0), b(0), c(0) {}
    long long value() {
        return a * (Ma + Mb) - Ma * (a + b);
    }
    bool operator<(Mixed& rhs) {
        long long this_value = value();
        long long rhs_value = rhs.value();
        return (this_value != rhs_value ? this_value < rhs_value : this->c < rhs.c);
    }
    bool operator<(long long target) {
        long long this_value = value();
        return (this_value < target);
    }
};


//実体化
long long Mixed::Ma;
long long Mixed::Mb;

int main() {
    long long N, Ma, Mb;
    cin >> N >> Ma >> Mb;

    Mixed::Ma = Ma;
    Mixed::Mb = Mb;

    vector<long long> a(N), b(N), c(N);
    for (int i = 0; i < N; i++) {
        cin >> a[i] >> b[i] >> c[i];
    }

    long long ans = INT_MAX;

    //前半を列挙
    long long half_N = (N + 1) / 2;
    vector<Mixed> half1;
    for (int i = 0; i < (1 << half_N); i++) {
        Mixed tmp;
        for (int j = 0; j < half_N; j++) {
            if (i & (1 << j)) {
                //立っていたらカウント
                tmp.a += a[j];
                tmp.b += b[j];
                tmp.c += c[j];
            }
        }
        if (tmp.a * tmp.b != 0 && Ma * tmp.b == Mb * tmp.a) {
            ans = min(ans, tmp.c);
        }
        half1.push_back(tmp);
    }

    //後半を列挙
    long long another_half = N - half_N;
    vector<Mixed> half2;
    for (int i = 0; i < (1 << another_half); i++) {
        Mixed tmp;
        for (int j = 0; j < another_half; j++) {
            if (i & (1 << j)) {
                //立っていたらカウント
                tmp.a += a[j + half_N];
                tmp.b += b[j + half_N];
                tmp.c += c[j + half_N];
            }
        }
        if (tmp.a * tmp.b != 0 && Ma * tmp.b == Mb * tmp.a) {
            ans = min(ans, tmp.c);
        }
        half2.push_back(tmp);
    }

    //後半の方をソート
    sort(half2.begin(), half2.end());

    for (auto m : half1) {
        //mと合わせて比が正しくなるものをhalf2の中から2分探索
        long long need = -m.value();
        auto pair = lower_bound(half2.begin(), half2.end(), need);
        if (pair == half2.end()) {
            continue;
        }
        //最小が取れていないか
        for (auto itr = pair; ; itr--) {
            long long value = itr->value();
            if (value != need) {
                break;
            }
            
            //確認
            long long sum_a = m.a + itr->a;
            long long sum_b = m.b + itr->b;
            if (sum_a * sum_b == 0) {
                continue;
            }
            if (Ma * sum_b == Mb * sum_a) {
                ans = min(ans, m.c + itr->c);
            }

            if (itr == half2.begin()) {
                break;
            }
        }
    }
    if (ans == INT_MAX) {
        ans = -1;
    }

    cout << ans << endl;
}

Measured memory_bytes: 63588
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ll x;
    cin>>x;
    ll a[x];
    for(int i=0;i<x;i++) {
        cin>>a[i];
    }
    int ans = 0;
    for(int i=0;i<x;i++) {
        for(int j=i+1;j<x;j++) {
            for(int k=j+1;k<x;k++) {
                if(a[i] == a[k] || a[i] == a[j] || a[k] == a[j]) continue;
                ll v[3];
                v[0] =  a[i];
                v[1] = a[j];
                v[2] = a[k];
                sort(v, v+3);
                if(v[0] + v[1] > v[2])ans++;

            }
        }
    }
    cout<<ans<<endl;
}


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

class dice{
    public :
    int d[6] ;
    void in(vector<int> &a){
        for(int i=0;i<6;i++) d[i] = a.at(i) ;
    }
    void roll(char c){
        if(c=='N'){
            int sub = d[0] ;
            d[0] = d[1] ;
            d[1] = d[5] ;
            d[5] = d[4] ;
            d[4] = sub ;
        }
        if(c=='S'){
            int sub = d[0] ;
            d[0] = d[4] ;
            d[4] = d[5] ;
            d[5] = d[1] ;
            d[1] = sub ;
        }
        if(c=='E'){
            int sub = d[0] ;
            d[0] = d[3] ;
            d[3] = d[5] ;
            d[5] = d[2] ;
            d[2] = sub ;
        }
        if(c=='W'){
            int sub = d[0] ;
            d[0] = d[2] ;
            d[2] = d[5] ;
            d[5] = d[3] ;
            d[3] = sub ;
        }
    }
} ;

int main(){
    vector<int> a(6) ;
    for(int i=0;i<6;i++) cin >> a.at(i) ;
    dice d ;
    d.in(a) ;
    string s ;
    cin >> s ;
    for(auto c:s){
        d.roll(c) ;
    }
    cout << d.d[0] << endl ;
}


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

int main() {
  int N, Y;
  cin >> N >> Y;
  int n = 0;
  int I, J, K;
  for(int i = 0; i <= N; i++) {
    for(int j = 0; j <= N - i; j++) {
      for(int k = 0; k <= N - i - j; k++) {
        if(Y == 10000 * i + 5000 * j + 1000 * k && N == i + j + k) {
          n++;
          I = i;
          J = j;
          K = k;
          break;
        }
      }
    }
  }
  if(n == 0) {
    cout << "-1 -1 -1" << endl;
  }
  else cout << I << " " << J << " " << K << endl;
}

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

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

const long long INF = 1LL << 60;

// 貰うDPでの実装
/*
int main() {
    int n;
    cin >> n;

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

    long long dp[n];
    for (int i = 0; i < n; ++i) dp[i] = INF;
    dp[0] = 0;
    for (int i = 1; i < n; ++i) {
        chmin(dp[i], dp[i - 1] + abs(h[i] - h[i - 1]));
        if (i > 1) chmin(dp[i], dp[i - 2] + abs(h[i] - h[i - 2]));
    }

    cout << dp[n - 1] << endl;
    return 0;
}
*/

// 配るDPでの実装
int main() {
    int N;
    cin >> N;

    long long H[N];
    for (int i = 0; i < N; ++i) cin >> H[i];

    long long dp[N];
    for (int i = 0; i < N; ++i) dp[i] = INF;
    dp[0] = 0;

    for (int i = 0; i < N; ++i) {
        if (i < (N - 1)) {
            chmin(dp[i + 1], dp[i] + abs(H[i] - H[i + 1]));
        }

        if (i < (N - 2)) {
            chmin(dp[i + 2], dp[i] + abs(H[i] - H[i + 2]));
        }
    }

    cout << dp[N - 1] << endl;
    return 0;
}

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

int N;
int H[100000];

int main() {
    cin >> N;
    rep(i, N) cin >> H[i];

    string ans = "Yes";
    for (int i = 0; i <= N - 2; i++) {
        // printf("%d %d\n", H[i], H[i + 1]);
        if (H[i] > H[i + 1]) {
            ans = "No";
            break;
        }

        H[i + 1] = max(H[i], H[i + 1] - 1);
    }

    cout << ans << endl;
}

Measured memory_bytes: 640
from collections import deque
h, w = map(int, input().split())
s = [input() for _ in range(h)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
def bfs(i, j):
    cost = [[-1 for _ in range(w)] for _ in range(h)]
    que = deque()
    cost[i][j] = 0
    que.append((i, j))
    if s[i][j] == '#':
        return 0
    while que:
        ni, nj = que.popleft()
        for k in range(4):
            if 0 <= ni+dy[k] < h and 0 <= nj+dx[k] < w:
                if cost[ni+dy[k]][nj+dx[k]] != -1:
                    continue
                if s[ni+dy[k]][nj+dx[k]] == '.':
                    cost[ni+dy[k]][nj+dx[k]] = cost[ni][nj]+1
                    que.append((ni+dy[k], nj+dx[k]))

    cc = 0
    for i in range(h):
        for j in range(w):
            if cost[i][j] > cc:
                cc = cost[i][j]
    return cc

ans = 0
for i in range(h):
    for j in range(w):
        cost = bfs(i, j)
        ans = max(ans, cost)

print(ans)


Measured memory_bytes: 9120
n,k,s=map(int,input().split())
a=[1 for i in range(n)]
for i in range(k):
    a[i]=s
for i in range(k,n):
    if s!=10**9:
        a[i]+=s
    else:
        a[i]=1
if k==0:
    if s!=10**9:
        a=[10**9 for i in range(n)]
    else:
        a=[1 for i in range(n)]
      
print(*a)

Measured memory_bytes: 89892
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i,n) for(ll i=0;i<n;i++)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define fi first
#define se second
#define endl "\n"

template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){int len=d.size();rep(i,len){s<<d[i];if(i<len-1) s<<" ";}return s;}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){int len=d.size();rep(i,len){s<<d[i]<<endl;}return s;}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){s<<"{"<<endl;for(auto itr=m.begin();itr!=m.end();++itr){s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;}s<<"}"<<endl;return s;}

const ll mod=1e9+7;
const ll inf=1e17;
const int INF=1e9;
const double PI=acos(-1);
const double EPS=1e-10;

int main(){
	cin.tie(0);ios::sync_with_stdio(false);
	ll n,m;
	cin>>n>>m;
	vector<ll> a(m);
	ll sum=0;
	rep(i,m){
		cin>>a[i];
		sum+=a[i];
	}
	n-=sum;
	if(n<0) cout<<-1<<endl;
	else cout<<n<<endl;
}

Measured memory_bytes: 3740
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i<(n);i++)
#define rep2(i,a,n) for(int i=a;i<n;i++)
#define been(ix) (ix).begin(),(ix).end()
using namespace std;
typedef long long ll; 
typedef vector<int> vi;
typedef vector<long long> vl;
const ll INFL = 1e18;
const int INF = 1001001001; 
typedef pair<int,int> P;
#define foreach(ix,i) for(auto& (ix) : (i))
typedef long double ld;
const int mod =1000000007;
const double PI = acos(-1);

int main(){
	int n;cin>>n;
	ll a[n];
	rep(i,n)cin>>a[i];
	ll sum[n+1];
	sum[0]=0;
	rep(i,n){
		sum[i+1]=sum[i]+a[i];
	}
	map<ll,ll>m;
	rep(i,n+1){
		m[sum[i]]++;
	}
	ll ans =0;
	for(auto x:m){
		ans+=(x.second*(x.second-1))/2;
	}
	cout<<ans<<endl;
}

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

int main(){

    int a,b,k;
    int ans,cnt=0;
    cin>>a>>b>>k;
    int gcd=__gcd(a,b);
    for(int i=gcd;i>=1;i--){
        if(gcd%i==0){
            cnt++;
            if(cnt==k) ans=i;
        }
    }
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    string S;
    cin >> S;

    int n = S.length();

    for (int i = 0; i < n; i++){
        if (i == 3){
            cout << 8;
        }
        else if (i == n - 1){
            cout << S[i] << endl;
        }
        else {
            cout << S[i];
        }
    }
}

Measured memory_bytes: 256
//#include<stdio.h>
//#include<stdlib.h>
#include<bits/stdc++.h>
//#define Min(a,b,c) min((a),min((b),(c)))
#define mp(a,b) make_pair((a),(b))
#define pii pair<int,int>
#define pll pair<LL,LL>
#define pb(x) push_back(x)
#define x first
#define y second
#define sqr(x) ((x)*(x))
#define EPS 1e-11
#define MEM(x) memset(x,0,sizeof(x))
//#define N 200005
#define M
#define pi 3.14159265359
using namespace std;
typedef long long LL;
int main(){
	int n;
	scanf("%d",&n);
	int a[100005];
	for(int i=0;i<n;i++)
	scanf("%d",&a[i]);
	int ans=0;
	int i=1;
	for(i=1;i<n;i++){
		int d=0,in=0;
		ans++;
		for(;i<n;i++){
			if(d&&a[i]>a[i-1])
			break;
			if(in&&a[i]<a[i-1])
			break;
			if(!d&&!in){
				if(a[i]>a[i-1])
				in=1;
				else if(a[i]<a[i-1])
				d=1;
			}
		}
	}
	if(i==n)
	ans++;
	printf("%d\n",ans);
}

/*90 110
180 220
270 330
360 440
450 550
540 660
630 770
*/

Measured memory_bytes: 640
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <unordered_map>

using namespace std;

typedef long long ll;

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    unordered_map<char, int> m1, m2, m3;
    m1[s[0]] = 1;
    for (int i = 1; i < n; i++) {
        if (m2.find(s[i]) != m2.end()) {
            m2[s[i]]++;
        } else
            m2[s[i]] = 1;
    }
    int max = 0;
    int tmp = 0;
    for (int i = 0; i < n - 1; i++) {
        for (auto j = m1.begin(); j != m1.end(); j++) {
            if (m2[j->first] > 0) {
                m3[j->first] = 1;
            }
        }
        if (m3.size() > max)
            max = m3.size();
        if (m1.find(s[i + 1]) != m1.end()) 
            m1[s[i + 1]]++;
        else
            m1[s[i + 1]] = 1;
        m2[s[i + 1]]--;
        m3.clear();
    }
    cout << max << endl;
    return 0;
}


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

#define rep(i,n) for(long long i=0; i<(long long)(n);i++)
#define rep2(i,s,n) for(long long i=(s); i<(long long)(n);i++)
#define mod 1000000007
typedef long long ll;

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

    if((a*b)%2==0){
        cout<<"Even"<<endl;
        return 0;
    }
    else {
        cout<<"Odd"<<endl;
    }

}


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

int main() {
  int n;
  cin >> n;
  vector<long long>data(n);
  for(int i = 0;i < n;i++){
    cin >> data[i];
  }
  sort(data.begin(),data.end());
  for(long long i = data[1];i > 0;i--){
    int c = 0;
    for(int j = 0;j < n;j++){
      if(data[j]%i != 0) c++;
      if(c == 2) break;
    }
    if(c < 2){
      cout << i << endl;
      return 0;
    }
  }
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a,b,c,x,ans=0;
	cin>>a>>b>>c>>x;
	for(int i=0;i<=a;i++)
		for(int j=0;j<=b;j++)
			for(int k=0;k<=c;k++)
				if(500*i+100*j+50*k==x)
					ans++;
	cout<<ans<<endl;
}


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

int main() {
    int n;
    cin >> n;
    for (int i = 1; i < 10; i++){
        for (int j = 1; j < 10; j++){
            if(i*j == n){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0,i##_len=int(n);i<i##_len;++i)
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define All(x) (x).begin(),(x).end()
#define rAll(x) (x).rbegin(),(x).rend()
using namespace std;
using ll = long long;

constexpr ll mod= 1e9+7;
vector<unordered_map<string,ll>> mp;
ll dfs(ll N,string last4){
    
    if(mp[N].count(last4)){
        return mp[N][last4];
    }
    if(last4.find("AGC")!=string::npos) return mp[N][last4]=0;
    REP(i,(int)last4.size()-1){
        swap(last4[i],last4[i+1]);
        if(last4.find("AGC")!=string::npos) return mp[N][last4]=0;
        swap(last4[i],last4[i+1]);
    } 
    if(N==0) return 1;
    string t=last4;
    if(t.size()==4) t.erase(t.begin());
    ll res=0;
    res+=dfs(N-1,t+'A');
    res+=dfs(N-1,t+'T');
    res+=dfs(N-1,t+'G');
    res+=dfs(N-1,t+'C');
    return mp[N][last4]=res%mod;
}

int main(){
    int N;cin>>N;
    mp.resize(N+1);
    cout<<dfs(N,"")<<endl;    
}


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

using namespace std;
int main() {
    string S;cin>>S;
    string ans;
    if(S=="Sunny"){
        ans="Cloudy";
    }
    else if(S=="Cloudy"){
        ans="Rainy";
    }
    else if(S=="Rainy"){
        ans="Sunny";
    }
    cout<<ans;
    return 0;
}

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

int main() {
	char in[8][8];
	int i, j, ans = 0, lop = 0;
	while (cin >> in[lop]) {
		if (++lop < 8)
			continue;
		lop = 0;
		ans = 0;
		for (i = 0; i < 8; i++) {
			for (j = 0; j < 8; j++) {
				if (in[i][j] == '1')
					goto end;
			}
		}
	end:
		if (in[i + 3][j] == '1') {
			ans = 1;
			goto out;
		}
		if (in[i][j+3] == '1') {
			ans = 2;
			goto out;
		}
		if (in[i + 2][j - 1] == '1') {
			ans = 3;
			goto out;
		}
		if (in[i + 1][j + 2] == '1') {
			ans = 4;
			goto out;
		}
		if (in[i + 2][j + 1] == '1') {
			ans = 5;
			goto out;
		}
		if (in[i + 1][j - 1] == '1') {
			ans = 6;
			goto out;
		}
	out:
		cout << (char)('A' + ans) << endl;
	}
	return 0;
}


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

typedef long long ll;
#define ten5 100000+10
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define iif(c,t,f) ((c)?(t):(f))
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair

int intcmp(const void *v1,const void *v2){return *(int *)v1-*(int *)v2;}

int h,w;

int paint[100][100];

int derx[]={0,0,1,-1};
int dery[]={1,-1,0,0};

int main(){
  cin>>h>>w;
  rep(i,1,h+1){
    char linev[100];
    scanf("%s",linev);
    rep(j,0,w){
      if(linev[j]=='#')
        paint[i][j+1]=1;
    }
  }
  bool ok =true;
  rep(i,1,h+1)
    rep(j,1,w+1){
      if(paint[i][j]){
        bool cnt = false;
        rep(k,0,4){
          if(paint[i+derx[k]][j+dery[k]])
            cnt=true;
        }
        if(!cnt)
          ok=false;
      }
    }
  cout<<(ok?"Yes":"No")<<endl;
  return 0;
}


Measured memory_bytes: 256
/*
  coded by: mi_ni_
  "LIVE LONG AND PROSPER"
*/
 
#include <bits/stdc++.h>
using namespace std;

#define FAST_IO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define newl '\n'
#define TEST_CASE(fun) int tc; cin>>tc; while(tc--){ fun(); }
#define TEST_CASE_2 int tc; cin>>tc; for(int i=1;i<=tc;i++)
#define TEST_CASE_3(fun) int tc; cin>>tc; for(int i=1;i<=tc;i++){ cout<<"Case #"<<i<<": "; fun(); }
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define forn(i,n) for(int i=0;i<(int)(n);i++)
#define forab(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define forabr(i,a,b) for(int i=(int)(a);i>=(int)(b);i--)
#define trav(i,x) for(auto& i:x)

using ll=long long int;
using ull=unsigned long long int;
using ld=long double;
using pii=pair<int, int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vl=vector<ll>;
using vii=vector<pii>;
using vll=vector<pll>;

const ld pi=acosl(-1);
const int inf=(int)1e9+7;
const ll llinf=(ll)1e18+7;
const ld eps=1e-7;

//other
template<typename T> inline bool powerof2(T a){ return (a&&(!(a&(a-1)))); }
template<typename T> inline T log_2(T a){ T res=-1; while(a){ a/=2; res++; } return res; }

//make sure to choose TEST_CASE in main for multiple test cases
void solve(){
	int n;
	string s;
	cin>>n>>s;
	int W=(int)count(all(s),'W');
	int cnt=0;
	forabr(i,n-1,n-W) if(s[i]=='R') cnt++;
	cout<<cnt<<newl;
}

int main(){
	FAST_IO
	cout<<fixed<<setprecision(15);
	cerr<<fixed<<setprecision(10);
	//init_fact();
	//TEST_CASE(solve)
	//TEST_CASE_2{}
	//TEST_CASE_3(solve)
	solve();
	return 0;
}

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

using namespace std;

constexpr int MOD = 1000000007;
using ll = long long;

#define MAX 100001
ll f[MAX], finv[MAX], inv[MAX];
void init() {
  f[0] = f[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < MAX; ++i) {
    f[i] = f[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}
ll C(int n, int r) {
  if (n < r || n < 0 || r < 0) {
    return 0;
  } else {
    return f[n] * (finv[r] * finv[n - r] % MOD) % MOD;
  }
}

int main() {
  int N, K;
  cin >> N >> K;
  init();
  vector<int> A(N);
  map<int, int> cnt;
  for (int i = 0; i < N; ++i) {
    cin >> A[i];
    cnt[A[i]]++;
  }
  ll ans = 0, lower_cnt = 0;
  for (auto p : cnt) {
    for (int i = 1; i <= min(p.second, K); ++i) {
      ll top = C(p.second, i) * C(lower_cnt, K - i) % MOD;
      ll bottom = C(p.second, i) * C(N - lower_cnt - p.second, K - i) % MOD;
      ans = (ans + (top - bottom + MOD) * (p.first + MOD) % MOD) % MOD;
    }
    lower_cnt += p.second;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 7296
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>
#define DEBUG true
#ifdef ONLINE_JUDGE
#undef DEBUG
#define DEBUG false
#endif 

using namespace std;

#define TRACE(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); cerr << endl;}

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << "[" << *it << " = " << a << "]";
	err(++it, args...);
}

#define MAXN ((ll)2e5+5)
#define MOD ((ll)1e9 + 7)
#define INF ((ll)1e9 + 9)
#define ll long long
#define _ << " " <<
#define CLEAR(a, b) memset(a, b, sizeof(a))
#define LOG(x) if(DEBUG) cerr << x << endl;
#define pb push_back
#define all(x) x.begin(), x.end()
#define endl "\n"
#define pii pair<ll,ll>
#define mid ((l+r)/2)

ll n,k;
ll d[MAXN];
ll pad, cycle;
vector <ll> v;
map <ll,ll> mp;

signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin >> n >> k;
	for (ll i = 1; i <= n; ++i)
		cin >> d[i];

	ll cur = 1, idx = 0;
	while(mp[cur] == 0)
	{
		mp[cur] = ++idx;
		v.pb(cur);
		cur = d[cur];
	}
	pad = mp[cur]-1;
	cycle = idx-pad;

	if(k < pad)
	{
		cout << v[k] << endl;
		return 0;
	}

	k-=pad;
	k %= cycle;

	cout << v[pad+k] << endl;
}

/* stuff you should look for
	* ll overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
*/

Measured memory_bytes: 18540
#include <cassert>
#include <cstddef>
#include <utility>
#include <vector>


template <class Abelian> class PotentializedUnionFind {

public:
	using value_type = Abelian;
	using difference_type = std::ptrdiff_t;
	using container_type = std::vector<std::pair<difference_type, value_type>>;
	using size_type = typename container_type::size_type;

protected:
	container_type c;

private:
	value_type potential(size_type x) {
		value_type ret = {};
		while (c[x].first >= static_cast<difference_type>(0)) {
			if (c[static_cast<size_type>(c[x].first)].first >=
				static_cast<difference_type>(0)) {
				c[x].second =
					c[static_cast<size_type>(c[x].first)].second + c[x].second;
				c[x].first = c[static_cast<size_type>(c[x].first)].first;
			}
			ret = ret + c[x].second;
			x = static_cast<size_type>(c[x].first);
		}
		return std::move(ret);
	}

public:
	PotentializedUnionFind() : c() {}
	explicit PotentializedUnionFind(const size_type size)
		: c(size, std::make_pair(-1, value_type())) {}

	size_type size() const { return c.size(); }
	bool empty() const { return c.empty(); }

	size_type find(size_type x) {
		assert(x < size());
		while (c[x].first >= static_cast<difference_type>(0)) {
			if (c[static_cast<size_type>(c[x].first)].first >=
				static_cast<difference_type>(0)) {
				c[x].second =
					c[static_cast<size_type>(c[x].first)].second + c[x].second;
				c[x].first = c[static_cast<size_type>(c[x].first)].first;
			}
			x = static_cast<size_type>(c[x].first);
		}
		return x;
	}
	value_type diff(const size_type x, const size_type y) {
		assert(x < size());
		assert(y < size());
		return potential(y) + (-potential(x));
	}
	bool same(const size_type x, const size_type y) {
		assert(x < size());
		assert(y < size());
		return find(x) == find(y);
	}
	size_type size(const size_type x) {
		assert(x < size());
		return static_cast<size_type>(-c[find(x)].first);
	}

	bool unite(size_type x, size_type y, value_type d) {
		assert(x < size());
		assert(y < size());
		d = d + diff(y, x);
		x = find(x);
		y = find(y);
		if (x == y)
			return false;
		if (c[x].first > c[y].first)
			std::swap(x, y), d = -d;
		c[x].first += c[y].first;
		c[y] = std::make_pair(static_cast<difference_type &&>(x), std::move(d));
		return true;
	}
};

#include<iostream>

int main() {
	int n, q;
	std::cin >> n >> q;
	PotentializedUnionFind<int> T(n);
	while (q--) {
		int t, x, y, z;
		std::cin >> t >> x >> y;
		if (t) {
			if (T.same(x, y))
				std::cout << T.diff(x, y) << std::endl;
			else
				std::cout << "?" << std::endl;
		}
		else {
			std::cin >> z;
			T.unite(x, y, z);
		}
	}
	return 0;
}



Measured memory_bytes: 4412
#include <cstdio>
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <cmath>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#define rep(i,n) for (int i=0;i<n;i++)
using ll = long long;
using namespace std;

void solve(){

}
int main (){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,k;
    cin >> n>>k;
    int ans =0;
    rep(i,n){
        int m;
        cin >> m;
        if(m>=k) ++ans;
    }
    cout << ans;

    return 0;
}

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

def solve(N: int, A: "List[int]"):
    result = {k+1:0 for k in range(N)}

    for idx, a in enumerate(A):
        idx = idx + 2
        result[a] += 1
    for k, v in result.items():
        print(v)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    A = [int(next(tokens)) for _ in range(N - 2 + 1)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


Measured memory_bytes: 54748
// Implementation practice (Have seen the editorial)
#include <bits/stdc++.h>
using namespace std;
#define debug(a) cout << #a << ": " << (a) << "\n"

const int N = 100 + 10;
int n, t[N], v[N], p[N];
double ans;

int main() {
	/*freopen("in", "r", stdin);
	freopen("out", "w", stdout);*/
	ios::sync_with_stdio(false);cin.tie(NULL);

	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> t[i],
		p[i+1] = p[i] + t[i];
	for (int i = 1; i <= n; i++) cin >> v[i];
	v[n+1] = 0;

	double le = 0, ml, mr;
	for (int i = 1; i <= n; i++) {
		ml = min((double)t[i], v[i]-le);
		mr = t[i];
		for (int j = i+1; j <= n+1; j++)
			if (le+mr-v[j] >= p[j]-(p[i]+mr))
				mr = (p[j]+v[j]-p[i]-le)/(double)2;
		ml = min(ml, mr);
		if (mr > ml) mr = min(mr+(mr-ml), (double)t[i]);
		ans += (le+ml+le)*ml/(double)2;
		ans += (le+ml+le+ml)*(mr-ml)/(double)2;
		ans += (le+ml+le+ml-(t[i]-mr))*(t[i]-mr)/(double)2;
		le = le+ml-(t[i]-mr);
	}

	cout << fixed << setprecision(15) << ans << endl;

	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {

		try (Scanner sc = new Scanner(System.in)) {
			String s = sc.next();
			String result = "";
			for (int i = 0; i < s.length(); i++) {
				result += "x";
			}
			System.out.println(result);
		}
	}

}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define ll long long 
#define PB push_back
#define lc 2 * v
#define rc 2 * v + 1
#define mid (s + e) / 2
#define pii pair <int,  int>
#define pll pair <long long , long long>  
#define FAST ios::sync_with_stdio(false);cin.tie(0);
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

const int maxn = 2e5 + 10 , INF = 1e9;


int main() {
    FAST
    char c;
    cin >> c;
    if(c >= 'a') {
        cout << 'a' << endl;
    }    
    else {
        cout << 'A' << endl;
    }
}

Measured memory_bytes: 3628