akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
#include<cstdlib>
#include<map>
#include<fstream>
#include<string>
#include<sstream>
#include<iomanip>
#include<cmath>
#include<random>
#include<set>
#include<queue>

using namespace std;

long long dp[3][100100] = {};
const long long INF = 1LL << 60;
#define MOD 1000000007
#define Int int64_t
#define PI 3.14159265358979
#define dump(a) cout << a << endl; 

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; }

/**
* @fn
* 最大値を取ります.Vector<int>を渡すこと.
*/
long long int imax(vector<int> a) {
	int MAX = -10000000;
	for (int i = 0; i < a.size(); i++) {
		if (MAX < a.at(i)) MAX = a.at(i);
	}
	return MAX;
}

/**
* @fn
* 最小値を取ります.Vector<int>を渡すこと.
*/
long long int imin(vector<int> a) {
	int MIN = 1000000000;
	for (int i = 0; i < a.size(); i++) {
		if (MIN > a.at(i)) MIN = a.at(i);
	}
	return MIN;
}

/**
* @fn
* 自然数について、桁数を求める
*/
Int getDigit(Int num) {
	return (Int)(log10(num)) + 1;
}


int get2Digit(Int num) {
	int cnt = 0;
	while (num > 0) {
		if (num % 2 != 0) {
			return cnt;
		}
		cnt++;
		num /= 2;
	}
}

long long int absmin(vector<int> a, long long int b) {
	int mini = 100000000;
	int d = 0;
	for (int i = 0; i < a.size(); i++) {
		if (mini > abs(a.at(i) - b)) {
			mini = abs(a.at(i) - b);
			d = i;
		}
	}
	return d;
}


long long int absmax(vector<int> a, long long int b) {
	int max = -100000000;
	int d = 0;
	for (int i = 0; i < a.size(); i++) {
		if (max < abs(a.at(i) - b)) {
			max = abs(a.at(i) - b);
			d = i;
		}
	}
	return d;
}

int gcd(int a, int b)
{
	if (a < b) swap(a, b);
	if (b < 1) return -1;
	if (a % b == 0) return b;
	return gcd(b, a % b);
}

void haerobatya(int start, int end, char level) {
	if (start > end) swap(start, end);
	for (int i = start; i <= end; i++) {
		if (i < 100) {
			cout << "https://atcoder.jp/contests/abc0" << i << "/tasks/abc0" << i << "_" << level << endl;
		}
		else {
			cout << "https://atcoder.jp/contests/abc" << i << "/tasks/abc" << i << "_" << level << endl;
		}
	}
}

long long int cntmod(long long int warareru, long long int mod) {
	long long int i = 0;
	for (i = 0; true; i++) {
		if (warareru % mod == 0 && warareru >= mod) {
			warareru /= mod;
		}
		else {
			return i;
		}
	}
}

void ansYes(bool a) {
	if (a == true) cout << "Yes" << endl;
	else cout << "No" << endl;
}

void ansYES(bool a) {
	if (a == true) cout << "YES" << endl;
	else cout << "NO" << endl;
}


Int euclidean_gcd(Int a, Int b) {
	while (true) {
		if (a < b) swap(a, b);
		if (!b) break;
		a %= b;
	}
	return a;
}

typedef pair<int, int> pai;


//ここまでライブラリ
//ここから本文

int main() {
	int a;
	cin >> a;
	bool ans = false;
	if (a == 3 || a == 5 || a == 7) ans = true;
	ansYES(ans);
}


Measured memory_bytes: 256
#include<stdio.h>
int A[50];
int F(int);
int F(int x){
  if(x==1||x==0){
    return A[x]=1;
  }else if(A[x]!=0){
   return A[x];
  }
  return A[x] = F(x-1)+F(x-2);
  
}
int main(){
  int a,b;
  scanf("%d",&a);
  b=F(a);
  printf("%d\n",b);
  return 0;

}



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

int main()
{
  int n;
  cin >> n;
  vector<int> a(n+1);
  vector<int> b(n);
  for(int i=0;i<=n;++i){
    cin >> a.at(i);
  }
  for(int i=0;i<n;++i){
    cin >> b.at(i);
  }
  
  long ans=0;
  for(int i=n-1;i>=0;--i){
    if(b.at(i)>=a.at(i+1)){
      b.at(i)-=a.at(i+1);
      ans+=a.at(i+1);
      a.at(i+1)=0;
      if(b.at(i)>=a.at(i)){
        b.at(i)-=a.at(i);
        ans+=a.at(i);
        a.at(i)=0;
      }else{
        a.at(i)-=b.at(i);
        ans+=b.at(i);
      }
    }else{
      a.at(i+1)-=b.at(i);
      ans+=b.at(i);
    }
  }
  
  cout << ans;
  return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<vector>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
using ll = long long;
using P = pair<int, int>;
#include<algorithm>
#include<math.h>
#include<map>
#include<queue>

int main(){
	ll a, b;
	cin >> a >> b;
	int c(1);
	int i(0);
	while (c < b) {
		--c;
		c += a;
		++i;
	}
	cout << i;
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using static System.Math;
using static System.Console;

namespace CPLib
{
    class Atria
    {
        static void Main(string[] args)
        {
            int n = int.Parse(ReadLine());
            int[] s = ReadLine().Split(' ').Select(int.Parse).ToArray();

            int sum = 0;
            for (int i = 0; i < n; i++)
            {
                sum ^= s[i];
            }
            var ls = new List<int>();
            for (int i = 0; i < n; i++)
            {
                ls.Add(sum ^ s[i]);
            }
            WriteLine(
                string.Join(" ",ls)
                );
        }
    }
}


Measured memory_bytes: 67432
#include <stdio.h>

int main(void){

  int n, m, l;
  int i, j, k;

  scanf("\n%d %d %d", &n, &m, &l);
  unsigned int a[n][m]; 
  unsigned int b[m][l]; 
  long long int c[n][l];

  //input
  for(i=0; i<n; i++){
    for(j=0; j<m; j++){
      scanf("\n%d", &a[i][j]);
    }
  }
  for(i=0; i<m; i++){
    for(j=0; j<l; j++){
      scanf("\n%d", &b[i][j]);
    }
  }

  //initialize c
  for(i=0; i<n; i++){
    for(j=0; j<l; j++){
      c[i][j]=0;
    }
  }

  //calc
  for(i=0; i<n; i++){
    for(j=0; j<l; j++){
      for(k=0; k<m; k++){
	c[i][j]=c[i][j]+a[i][k]*b[k][j];
      }
    }
  }

  //output
  for(i=0; i<n; i++){
    for(j=0; j<l; j++){
      if(j==l-1){printf("%lld\n", c[i][j]);}
      else {printf("%lld ", c[i][j]);}
    }
  }

  return 0;

}

Measured memory_bytes: 756
#include<iostream>
#include<sstream>
#include<vector>
#include<iterator>
using namespace std;

int main(void)
{
	int N, M;
	cin >> N >> M;

	int ret = 1;
	for(int i=1; i*i<=M; i++){
		if(M%i != 0)
			continue;
		
		int j = M / i;
		if(j >= N)
			ret = max(ret, i);
		if(i >= N)
			ret = max(ret, j);
	}

	cout << ret << endl;

	return 0;
}


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

long dp[1000000];
long dpo[1000000];

int main(){
    int N;
    dp[0] = 0;
    dp[0] = 0;
    for(int i = 1;i < 1000000;i++){
            dp[i] = 1000000;
            dpo[i] = 1000000;
        }
    for(int i= 0;i < 1000;i++){
        long a = (i * (i + 1) * (i + 2)) / 6;
        for(int j = a;j < 1000000;j++){
            dp[j] = min(dp[j],dp[j - a] + 1);
            if(a % 2 == 1){
                dpo[j] = min(dpo[j],dpo[j - a] + 1);
            }
        }
    }
    for(int i = 0;;i++){
        scanf("%d",&N);
        if(N == 0){
            break;
        }
        printf("%ld %ld\n",dp[N],dpo[N]);
    }
    return 0;
}


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

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

ll N;
string s[200];
ll t[200];
ll m[200][200];
vector<vector<ll>> G;

bool dfs(ll n){
    ll count = 0;
    for(auto &e : G[n]){
        if(t[e] == 0) count++;
        if(t[e] == t[n]) return false;
    }
    if(count == 0) return true;
    for(auto &e : G[n]){
        if(t[e] != 0) continue;
        t[e] = (t[n] == 1) ? 2 : 1;
        if(!dfs(e)) return false;
    }
    return true;
}

int main(){
    cin >> N;
    G.resize(N);
    for(int i=0;i<N;i++) cin >> s[i];
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(s[i][j] == '0') m[i][j] = 1e9;
            else{
                m[i][j] = 1;
                G[i].push_back(j);
                G[j].push_back(i);
            }
        }
    }
    t[0] = 1;
    if(!dfs(0)){
        cout << -1 << endl;
        return 0;
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(s[i][j] == '0') m[i][j] = 1e9;
            else m[i][j] = 1;
        }
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            for(int k=0;k<N;k++){
                m[j][k] = min(m[j][k], m[j][i] + m[i][k]);
            }
        }
    }
    ll l = 0;
    for(int i=0;i<N;i++){
        for(int j=i+1;j<N;j++){
            l = max(l,m[i][j]);
        }
    }
    cout << l+1 << endl;
    return 0;
}

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

int main() {

    int H, N;
    cin >> H >> N;
    vector<int> A(N), B(N);
    rep(i, N) cin >> A[i] >> B[i];

    vector<ll> dp(H + 1, INF);
    dp[0] = 0;

    for (int i = 0; i <= H; i++) {
        if (dp[i] != INF) {
            rep(j, N) {
                if (i + A[j] >= H)
                    dp[H] = min(dp[H], dp[i] + B[j]);
                else
                    dp[i + A[j]] = min(dp[i + A[j]], dp[i] + B[j]);
            }
        }
    }

    cout << dp[H] << endl;

    return 0;
}

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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef long long ll;

const int MOD = 1000000007;

const int INF = 1001001001;

int main() {
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> key;
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        int s = 0;
        rep(j, b) {
            int c;
            cin >> c;
            c--;
            s |= 1 << c;
        }
        key.emplace_back(s, a);
    }

    vector<int> dp(1 << n, INF);
    dp[0] = 0;
    rep(s, 1 << n) {
        rep(i, m) {
            int t = s | key[i].first;
            int cost = dp[s] + key[i].second;
            dp[t] = min(dp[t], cost);
        }
    }
    int ans = dp.back();
    if (ans == INF) ans = -1;
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define MaxN 550
struct node
{
    int C;
    int S;
    int F;
}Node[MaxN];
int main()
{
    int N;
    scanf("%d",&N);
    for(int i=1;i<=N-1;i++)
        scanf("%d %d %d",&Node[i].C,&Node[i].S,&Node[i].F);
    for(int i=1;i<=N-1;i++)
    {
        int now_time=0;
        for(int k=i;k<=N-1;k++)
        {
            if(now_time<Node[k].S)
                now_time=Node[k].S;
            else
            {
                int sb=(now_time-Node[k].S)%Node[k].F;
                
                if(sb==0)
                    sb+=Node[k].F;//printf("%d\n",sb);
                now_time+=(Node[k].F-sb);
            
            }
            now_time+=Node[k].C;
          //  printf("%d\n",now_time);
        }
        printf("%d\n",now_time);
    }
    printf("0\n");
    return 0;
}


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

using namespace std;

#define INF 1000007
#define MOD 1000000007
#define int long long int
#define maxn 100
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, n) FOR(i, 0, n)

typedef std::pair<int, int> P;

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

int lcm(int a, int b) { return a / gcd(a, b) * b; }

int mpow(int N, int P, int M) //繰り返し自乗法
{
    if (P == 0)
        return 1;
    if (P % 2 == 0) {
        int t = mpow(N, P / 2, M);
        return t * t % M;
    }
    return N * mpow(N, P - 1, M) % M;
}

int counter(int x) //bit計算
{
    if (x == 0)
        return 0;
    return counter(x >> 1) + (x & 1);
}

vector<bool> prime(maxn + 1, true); //素数テーブル
void prime_table(void) {
    prime[0] = false;
    prime[1] = false;
    for (int i = 2; i * i <= maxn; i++) {
        if (!prime[i]) {
            continue;
        }
        for (int j = i + i; j <= maxn; j += j + i) {
            prime[j] = false;
        }
    }
}

bool IsPrime(int num) //素数判定
{
    if (num < 2)
        return false;
    else if (num == 2)
        return true;
    else if (num % 2 == 0)
        return false;

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2) {
        if (num % i == 0) {
            return false;
        }
    }

    return true;
}

vector<int> divisor(int n) //約数列挙
{
    vector<int> ret;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i - 1);
            if (i * i != n) {
                ret.push_back((n / i) - 1);
            }
        }
    }
    sort(ret.begin(), ret.end());
    return (ret);
}

signed main() {
    int N, A, B;
    cin >> N >> A >> B;
    int plus;
    if (N % (A + B) >= A) {
        plus = A;
    } else {
        plus = N % (A + B);
    }
    cout << A * (N / (A + B)) + plus << endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#include <fstream>
#include <iterator>
#include <sstream>
#include <bitset>
using namespace std;

// Debug Vector
template <typename T>
std::ostream &operator<<(std::ostream &out, const std::vector<T> &v)
{
    if (!v.empty())
    {
        out << '[';
        std::copy(v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
        out << "\b\b]";
    }
    return out;
}

template <typename T1, typename T2>
std::ostream &operator<<(std::ostream &out, const std::pair<T1, T2> &p)
{
    out << "[" << p.first << ", " << p.second << "]";
    return out;
}

typedef long long ll;

ll odd(ll a)
{
    return (a + 1) / 2 % 2;
}

ll solve(ll a)
{
    if (a % 2 == 1)
    {
        return odd(a);
    }
    else
    {
        return odd(a + 1) ^ (a + 1);
    }
}

int main()
{
    long long A, B;
    cin >> A >> B;
    long long ans = solve(B) ^ solve(A - 1);
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main() {
	rep(i, 3) {
		char n;
		cin >> n;
		if (n == '1') {
			cout << 9;
		}
		if (n == '9') {
			cout << 1;
		}
	}
	cout << endl;
}	

Measured memory_bytes: 3584
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
#define pb push_back
#define __V vector
#define all(x) x.begin(), x.end()
#define oit ostream_iterator
#define mod 1000000007ll
using namespace std;
void doin() {
	cin.tie();
	cout.tie();
	ios::sync_with_stdio(0);
#ifndef ONLINE_JUDGE
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
}
template<typename X, typename Y>
istream& operator>>(istream& in, pair<X, Y> &a) {
	in >> a.first >> a.second;
	return in;
}
template<typename T>
void getv(T& i) {
	cin >> i;
}
template<typename T, typename ... Ns>
void getv(vector<T>& v, int n, Ns ... ns) {
	v.resize(n);
	for (auto& i : v)
		getv(i, ns...);
}
template<typename T>
void getv1(T& i) {
	cin >> i;
}
template<typename T, typename ... Ns>
void getv1(vector<T>& v, int n, Ns ... ns) {
	v.resize(n + 1);
	for (int i = 1; i <= n; i++)
		getv(v[i], ns...);
}
#ifdef _WIN32
#define getchar_unlocked() _getchar_nolock()
#define _CRT_DISABLE_PERFCRIT_LOCKS
#endif
inline void getch(char &x) {
	while (x = getchar_unlocked(), x < 33) {
		;
	}
}
inline void getstr(string &str) {
	str.clear();
	char cur;
	while (cur = getchar_unlocked(), cur < 33) {
		;
	}
	while (cur > 32) {
		str += cur;
		cur = getchar_unlocked();
	}
}
template<typename T> inline bool sc(T &num) {
	bool neg = 0;
	int c;
	num = 0;
	while (c = getchar_unlocked(), c < 33) {
		if (c == EOF)
			return false;
	}
	if (c == '-') {
		neg = 1;
		c = getchar_unlocked();
	}
	for (; c > 47; c = getchar_unlocked())
		num = num * 10 + c - 48;
	if (neg)
		num *= -1;
	return true;
}
typedef unsigned long long ull;
typedef long long ll;
typedef float ld;
typedef ll _I;
typedef pair<_I, _I> pi;
typedef pair<ld, ld> pd;
typedef map<_I, _I> mii;
typedef __V <_I> vi;
typedef __V <char> vc;
typedef __V <ld> vd;
typedef __V <vd> vvd;
typedef __V <pi> vpi;
typedef __V <__V<_I>> vvi;
typedef __V <__V<char>> vvc;
typedef __V <__V<pi>> vvpi;
using AntonTsypko = void;
using arsijo = AntonTsypko;
using god = arsijo;
uniform_real_distribution<double> double_dist(0, 1);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int main() {
	doin();
	string s;
	int ans;
	cin >> s;
	int l = 0;
	for(auto i : s)
		if(i == 'A' || i == 'T' || i == 'C' || i == 'G')
			ans = max(ans, ++l);
		else
			l = 0;
	cout << ans;
	return 0;
}


Measured memory_bytes: 256
using namespace std;
#include<iostream>
#include<bits/stdc++.h>
#include<algorithm>
#define w(x) int x;cin>>x;while(x--)
#define FIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define MOD 1e9+7
#define ll long long

void abc()
{
	FIO;
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}








int main()
{
	abc();
	int x;
	cin >> x;
	if (x == 0) cout << 1;
	else cout << 0;








}










Measured memory_bytes: 3648
/*input
3
1 2 2
2 3 1
*/
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
typedef long double ld;
typedef long long ll;
using namespace std;
vector<pair<int, int>>adj[101010];
int color[101010];
void dfs(int i, int p)
{
	for (pair<int, int>j : adj[i])
	{
		if (j.first != p)
		{
			color[j.first] = (color[i] + j.second) % 2;
			dfs(j.first, i);
		}
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	int N;
	cin >> N;
	for (int i = 2; i <= N; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back({v, w % 2});
		adj[v].push_back({u, w % 2});
	}
	color[1] = 0;
	dfs(1, 1);
	for (int i = 1; i <= N; i++)
		cout << color[i] << " ";
}

Measured memory_bytes: 7680
N = int(input())
number = list(map(int,input().split()))

flag = 1
i = 0
count = 0
while flag==1:
    flag = 0
    for j in range(i+1,len(number))[::-1]:
        if number[j] < number[j-1]:
            temp  = number[j]
            number[j] = number[j-1]
            number[j-1] = temp
            flag = 1
            count += 1
    i += 1


print(" ".join(map(str,number)))
print (count)


Measured memory_bytes: 5596
import java.util.Scanner;

public class Main{

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

	int[][] tiles = new int[10][10];

	while (sc.hasNextLine()) {
	    String[] input = sc.nextLine().split(",");

	    if ("".equals(input[0])) {
		break;
	    }
	    int x = Integer.parseInt(input[0]);
	    int y = Integer.parseInt(input[1]);
	    int size = Integer.parseInt(input[2]);

	    if (1 == size) {
		for (int i = -1; i < 2; i++) {
		    if (i == 0) {
			if (compBet(y - 1)) {
			    tiles[x][y - 1]++;
			}

			if (compBet(y + 1)) {
			    tiles[x][y + 1]++;
			}
		    }

		    if (compBet(x + i)) {
			tiles[x + i][y]++;
		    }

		}
	    }

	    if (2 == size) {
		for (int i = -1; i < 2; i++) {
		    for (int j = -1; j < 2; j++) {
			if (compBet(x + i) && compBet(y + j)) {
			    tiles[x + i][y + j]++;
			}
		    }
		}
	    }

	    if (3 == size) {
		for (int i = -1; i < 2; i++) {
		    for (int j = -1; j < 2; j++) {
			if (compBet(x + i) && compBet(y + j)) {
			    tiles[x + i][y + j]++;
			}
		    }
		}
		if (compBet(x - 2)) {
		    tiles[x - 2][y]++;
		}

		if (compBet(x + 2)) {
		    tiles[x + 2][y]++;
		}

		if (compBet(y - 2)) {
		    tiles[x][y - 2]++;
		}

		if (compBet(y + 2)) {
		    tiles[x][y + 2]++;
		}

	    }

	}
	System.out.println(countZero(tiles));
	System.out.println(countMax(tiles));

    }

    private static boolean compBet(int xPlusI) {
	if (xPlusI <= -1) {
	    return false;
	}

	if (xPlusI >= 10) {
	    return false;
	}

	return true;
    }

    private static int countMax(int[][] tiles) {
	int max = 0;

	for (int[] yLine : tiles) {
	    for (int tile : yLine) {
		max = Math.max(max, tile);
	    }
	}
	return max;
    }

    private static int countZero(int[][] tiles) {
	int blankCount = 0;

	for (int[] yLine : tiles) {
	    for (int tile : yLine) {
		if (tile == 0) {
		    blankCount++;
		}
	    }
	}

	return blankCount;
    }
}

Measured memory_bytes: 25720
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <cstring>
#include <functional>
using namespace std;
typedef long long ll;
typedef pair<long long, long long> P;
#define rep(i, n) for(long long i=0; i<n; i++)
#define reps(i, s, e) for(long long i=s; i<e; i++)
#define repr(i, n) for(long long i=n-1; i>=0; i--)
#define reprs(i, s, e) for(long long i=e-1; i>=s; i--)

int main(){

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

    ll x, y, z, k; cin >> x >> y >> z >> k;
    ll a[x], b[y], c[z];
    rep(i, x){
        cin >> a[i];
    }
    rep(i, y){
        cin >> b[i];
    }
    rep(i, z){
        cin >> c[i];
    }

    vector<ll> ab_temp;
    rep(i, x){
        rep(j, y){
            ab_temp.push_back(a[i] + b[j]);
        }
    }

    sort(ab_temp.begin(), ab_temp.end(), greater<ll>());
    sort(c, c+z, greater<ll>());

    vector<ll> ab;
    rep(i, min(3000ll, x*y)){
        ab.push_back(ab_temp[i]);
    }

    // rep(i, ab.size()){
    //     cout << ab[i] << endl;
    // }

    priority_queue<pair<ll, P>> pq;
    bool isUsed[ab.size()][z] = {};

    ll i_ab = 0, i_c = 0;
    pq.push({ab[i_ab] + c[i_c], {i_ab, i_c}});
    isUsed[i_ab][i_c] = true;

    rep(i, k){
        pair<ll, P> ptemp = pq.top();
        pq.pop();
        ll tasty = ptemp.first;
        i_ab = ptemp.second.first;
        i_c  = ptemp.second.second;

        cout << tasty << endl;

        if(i_ab + 1 < ab.size() && !isUsed[i_ab+1][i_c]){
            pq.push({ab[i_ab+1] + c[i_c], {i_ab+1, i_c}});
            isUsed[i_ab+1][i_c] = true;
        }
        if(i_c + 1  < z && !isUsed[i_ab][i_c+1]){
            pq.push({ab[i_ab] + c[i_c+1], {i_ab, i_c+1}});
            isUsed[i_ab][i_c+1] = true;
        }
    }

    return 0;
}

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

inline int read()
{
	int N=0,C=0;char tf=getchar();
	for(;!isdigit(tf);tf=getchar())C|=tf=='-';
	for(;isdigit(tf);tf=getchar())N=(N<<1)+(N<<3)+(tf^48);
	return C?-N:N;
}

int a,b,c,t;
long long ans;

int main()
{
	// freopen("monkey.in","r",stdin);
	// freopen("monkey.out","w",stdout);
    a=read(),b=read(),c=read();
    t=min(a,c);
    a-=t,c-=t,ans+=t;
    if(a)ans+=b;
    else
    {
        t=min(b,c);
        b-=t,c-=t,ans+=(t<<1);
        if(b)ans+=b;
    }
    if(c)++ans; 
    printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 256
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            vars()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)


def bis(K, A, B, t):
    # K 番目に小さい <=> x 未満の数が K 個未満であるような最大の x
    if t==1:
        ok = 0
        ng = 10**18+1
        while ok + 1 < ng:
            c = ok+ng>>1
            cnt = 0
            idx_B = len(B)-1
            for a in A:
                while idx_B >= 0 and a * B[idx_B] >= c:
                    idx_B -= 1
                cnt += idx_B + 1
            if cnt < K:
                ok = c
            else:
                ng = c
    else:
        ok = 0
        ng = 10**18+1
        while ok + 1 < ng:
            c = ok+ng>>1
            cnt = 0
            idx_A = len(A)-1
            idx_B = len(B)-1
            for a in A:
                while idx_A >= 0 and a * A[idx_A] >= c:
                    idx_A -= 1
                cnt += idx_A + 1
                if a*a < c:
                    cnt -= 1
            for b in B:
                while idx_B >= 0 and b * B[idx_B] >= c:
                    idx_B -= 1
                cnt += idx_B + 1
                if b*b < c:
                    cnt -= 1
            cnt >>= 1
            if cnt < K:
                ok = c
            else:
                ng = c
    return ok

numba_compile([
    [bis, "i8(i8,i8[:],i8[:],i8)"],
])

import numpy as np
def main():
    N, K = map(int, input().split())
    A = sorted(map(int, input().split()))
    cnt_m = cnt_0 = cnt_p = 0
    for a in A:
        if a < 0:
            cnt_m += 1
        elif a == 0:
            cnt_0 += 1
        else:
            cnt_p += 1
    cnt2_m = cnt_m * cnt_p
    cnt2_0 = cnt_0 * N - cnt_0 * (cnt_0 + 1) // 2
    cnt2_p = cnt_p * (cnt_p - 1) // 2 + cnt_m * (cnt_m - 1) // 2
    assert cnt2_m + cnt2_0 + cnt2_p == N * (N - 1) // 2

    if K <= cnt2_m:
        # 絶対値が cnt2_m - K + 1 番目に小さい
        X = np.array([-a for a in A[::-1] if a<0], dtype=np.int64)
        Y = np.array([a for a in A if a>0], dtype=np.int64)
        ans = -bis(cnt2_m-K+1, X, Y, 1)
    elif K <= cnt2_m + cnt2_0:
        ans = 0
    else:
        X = np.array([-a for a in A[::-1] if a<0], dtype=np.int64)
        Y = np.array([a for a in A if a>0], dtype=np.int64)
        ans = bis(K-cnt2_m-cnt2_0, X, Y, 2)
    print(ans)

main()


Measured memory_bytes: 47860
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
	int n,k,x,y;
	cin>>n>>k>>x>>y;
	int ans=0;
	
	if(k<n){
		for(int i=1;i<=k;i++){
		ans+=x;
		}
		for(int i=k+1;i<=n;i++){
			ans+=y;
		}
	}
	else{
		for(int i=0;i<n;i++){
			ans+=x;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define sol (k+k)
#define sag (k+k+1)
#define orta (bas + (son-bas)/2)
#define coc g[node][i]
#define mod 1000000007
#define inf 1e18
#define N 1000005
#define lim 10000
using namespace std;

typedef long long ll;

int b[3][3],n,ar[N],t,a[30][30],ans;


int main()
{

	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);

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

	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		cin >> t;
		ar[t]++;
	}

	for (int i = 0; i < 3; ++i)
	{
		for (int j = 0; j < 3; ++j)
		{
			if(ar[b[i][j]] > 0)
				a[i][j] = 1;
		}
	}


	bool ch = false;
	if(a[0][0] && a[0][1] && a[0][2]) ch = true;
	if(a[1][0] && a[1][1] && a[1][2]) ch = true;
	if(a[2][0] && a[2][1] && a[2][2]) ch = true;
	if(a[0][0] && a[1][0] && a[2][0]) ch = true;
	if(a[0][1] && a[1][1] && a[2][1]) ch = true;
	if(a[0][2] && a[1][2] && a[2][2]) ch = true;
	if(a[0][0] && a[2][2] && a[1][1]) ch = true;
	if(a[2][0] && a[1][1] && a[0][2]) ch = true;
	if(ch) cout<<"Yes";
	else cout<<"No";

    return 0;
}


Measured memory_bytes: 256
n,q=map(int,input().split())
s=input()
t=[0]*(n+1)
for i in range(n-1):
    t[i+1]=t[i]+(1 if s[i:i+2]=="AC" else 0)
for i in range(q):
    l,r=map(int,input().split())
    print(t[r-1]-t[l-1])

Measured memory_bytes: 9284
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(){
	int N, M;
	cin >> N >> M;

	int a[100010] = { 0 };
	for (int i = 1; i <= M; i++) {
		cin >> a[i];
	}
	int dp[100010];

	dp[0] = 1;
	dp[1] = 1;
	int now = 1;
	if (a[now] == 1) {
		dp[1] = 0; now++;
	}

	for (int i = 2; i <= N; i++) {
		dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
		if (a[now] == i) {
			dp[i] = 0; now++;
		}
	}
	cout << dp[N];
}

Measured memory_bytes: 1024
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, k = LI()
    ans = 1
    dp = [i for i in range(n + 1)]
    dp = [i for i in itertools.accumulate(dp)]
    for i in range(k, n + 1):
        ans += (dp[n] - (dp[-i - 1])) - dp[i - 1] + 1
        ans %= mod
    print(ans)
    return


#main
if __name__ == '__main__':
    solve()


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

  public static void main(String[] args) { 
      Scanner sc = new Scanner(System.in);
      long x = sc.nextLong();
      long y = sc.nextLong();
      int cnt = 1;
      long cur = x;
      while(cur <= y / 2) {
        cur = cur * 2;
        cnt++;
      }
      System.out.println(cnt);
  }
}

Measured memory_bytes: 22612
#include<iostream>

long long int a[31];

int main(){
	int n;
	a[0] = 1, a[1] = 1, a[2] = 2;
	for (int i = 3; i <= 30; ++i){
		a[i] = a[i - 1] + a[i - 2] + a[i - 3];
	}
	while (std::cin >> n ,n){
		
		std::cout << (a[n]/3650)+1 << std::endl;
	}
}

Measured memory_bytes: 1156
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()

vector<int> IntegerToVector(int bit, int N) {
    vector<int> S;
    for (int i = 0; i < N; ++i) {
        if (bit & (1 << i)) {
            S.push_back(i);
        }
    }
    return S;
}

int main(){
    int N,A,x,y;
    cin >> N;
    vector<vector<pair<int,int>>> syogen(N);
    rep(i,N){
        cin >> A;
        rep(j,A){
            cin >> x >> y;
            syogen.at(i).push_back(make_pair(x-1,y));
        }
    }

    int mx =0;

    //bit全探索正直者が１
    for(int bit = 0; bit< (1 << N); bit++){
        vector<int> syojiki = IntegerToVector(bit,N);

        bool ok = true;

        //正直者の証言すべての裏を取る
        for(int i:syojiki){
            for(auto p:syogen.at(i)){
                if(p.second == 1){
                    if(find(all(syojiki),p.first) == syojiki.end()){
                        ok = false;
                        break;
                    }
                }else{
                    if(find(all(syojiki),p.first) != syojiki.end()){
                        ok = false;
                        break;
                    }
                }
            }
            if(not ok)break;
        }

        if(ok){
            int num = syojiki.size();
            mx = max(mx,num);
        }
    }

    cout << mx << endl;
}   

Measured memory_bytes: 256
from itertools import combinations
n=int(input())
dp=[0]*5
for i in range(n):
  s=input()
  if s[0]=="M":
      dp[0]+=1
  if s[0]=="A":
      dp[1]+=1
  if s[0]=="R":
      dp[2]+=1
  if s[0]=="C":
      dp[3]+=1
  if s[0]=="H":
      dp[4]+=1
ans=0
for a,b,c in combinations(dp,3):
  ans+=a*b*c
print(ans)


Measured memory_bytes: 74552
import java.util.Arrays;
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {	
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		Node[] node = new Node[num];
		for(int i=0;i<num;i++) {//创建结点个数
			node[i] = new Node();
		}
		for(int i=0;i<num;i++) {
			int id = sc.nextInt();
			int count = sc.nextInt();
			int[] c = new int[count];
			for(int j=0;j<count;j++) {
				c[j]=sc.nextInt();
				node[c[j]].parent=id;
			}
			node[id].child = c;
		}
		for(int i=0;i<num;i++) {
			node[i].depth(node, 0,i);
		}
		for(int i=0;i<num;i++) {
			System.out.println("node "+ i+": "+"parent = "+node[i].parent+", depth = "+node[i].depth+", "+node[i].type+", "+Arrays.toString(node[i].child));
		}
		
	}
}

class Node {
	
	int parent = -1;
	int[] child;
	int depth;
	String type;
	
	public  void depth(Node[] node,int depth,int i) {
			int p = node[i].parent;	
			if(p==-1) {
			this.depth=depth;
			if(parent==-1) {
				type = "root";
			}else if(child.length==0) {
				type="leaf";
			}else {
				type="internal node";
			}
			return;
		}
		depth(node,depth+1,p);	
	}

	
	

}



Measured memory_bytes: 131708
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <iterator>
#include <climits>
#include <unordered_map>
#include <queue>


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

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

inline int ctoi(char c) {
    return (int)(c -'0');
}

// ----------------------------------------------------------

int main() {
    ll a, b, c;
    cin >> a >> b >> c;
    if (a == 1) {
        cout << "Hello World" << endl;
        return 0;
    }
    cout << b + c << endl;
    return 0;
}

Measured memory_bytes: 256
#! /usr/bin/python
# -*- coding: utf-8 -*-

n = int(raw_input())
for i in range(n):
    ger = raw_input()
    mes = raw_input()
    
    for j in range(len(ger)-1, -1, -1):
        if ger[j] == 'J':
            mes = mes[len(mes)-1]+mes[0:len(mes)-1]
        elif ger[j] == 'C':
            mes = mes[1:len(mes)]+mes[0]
        elif ger[j] == 'E':
            if len(mes)%2 == 0:
                mes = mes[len(mes)/2:]+mes[0:len(mes)/2]
            else:
                mes = mes[len(mes)/2+1:]+mes[len(mes)/2]+mes[0:len(mes)/2]
        elif ger[j] == 'A':
            mes = mes[::-1]
        elif ger[j] == 'P':
            for k in range(len(mes)):
                if '1' <= mes[k] <= '9':
                    mes = mes[:k]+chr(ord(mes[k])-1)+mes[k+1:]
                    #mes[k] = chr(ord(mes[k])-1)
                elif mes[k] == '0':
                    mes = mes[:k]+'9'+mes[k+1:]
        elif ger[j] == 'M':
            for k in range(len(mes)):
                if '0' <= mes[k] <= '8':
                    mes = mes[:k]+chr(ord(mes[k])+1)+mes[k+1:]
                    #mes[k] = chr(ord(mes[k])+1)
                elif mes[k] == '9':
                    mes = mes[:k]+'0'+mes[k+1:]
    print mes
    

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

#define DEBUG(x) cout << "DEBUG>" << #x << ":" << x << endl;
#define REP(i,n) for(long long i=0;i<(n);i++)
#define FOR(i,a,b) for(long long i=(a);i<=(b);i++)

int main() {
  long long N, P;
  cin >> N >> P;
  map<long long, long long> res;
  long long ans = 1;
  for(long long i = 2; i * i <= P; i++) {
    while(P % i == 0) {
      res[i]++;
      P /= i;
    }
    if(res[i] >= N) {
      long long a = (res[i] - res[i] % N) / N;
      REP(j, a) {
        ans *= i;
      }
    }
  }
  if(P != 1) {
    res[P] = 1;
    if(res[P] >= N) {
      ans *= P;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 26240
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

struct edge {
    int to, id;
};

vector<vector<edge>> g;
vector<int> es;
bool dfs(int now, int goal, int pre) {
    if (now == goal) {
        return true;
    }
    for (edge e : g[now]) {
        int nxt = e.to;
        if (nxt == pre) continue;
        if (dfs(nxt, goal, now)) {
            es.push_back(e.id);
            return true;
        }
    }
    return false;
}

int main() {
    int n;
    cin >> n;
    g.resize(n);
    rep(i, n - 1) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        g[a].push_back((edge){b, i});
        g[b].push_back((edge){a, i});
    }

    int m;
    cin >> m;
    vector<ll> cons(m);
    rep(i, m) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        es = vector<int>();
        dfs(u, v, -1);
        for (int e : es) {
            cons[i] |= 1LL << e;
        }
    }

    ll ans = 0;
    for (ll mask = 0; mask < (1 << m); mask++) {
        ll now = 0;
        rep(i, m) {
            if (mask & (1 << i)) {
                now |= cons[i];
            }
        }

        int cnt = n - 1 - __builtin_popcountll(now);
        if (__builtin_popcountll(mask) % 2 == 0) {
            ans += (1LL << cnt);
        } else {
            ans -= (1LL << cnt);
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
double a[1500], ans=0;
int main() {
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		ans=ans+1/a[i];
	}
	cout << 1/ans << endl;
	return 0;
}

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

const int MAX_L = 10000;

int N, K, T, U, V, L;
bool carrots[MAX_L + 1];

double solve(){
	int cs = 0, boost_stop = 0;
	double time = 0;

	for(int p=0; p<L; p++){
		if(carrots[p]){
			cs++;
		}
		if(cs == K + 1 || (cs > 0 && boost_stop <= p) ){
			cs--;
			boost_stop = p + T * V;
		}

		time += 1.0 / (p < boost_stop ? V : U);
	}

	return time;
}

int main(){
	scanf("%d%d%d%d%d%d",&N, &K, &T, &U, &V, &L);
	for(int i=0; i<N; i++){
		int x;
		scanf("%d",&x);
		carrots[x] = true;
	}

	printf("%.10f\n", solve());

	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
int main()
{
	int a,b;
	cin>>a>>b;
	if(a>0&&b>0)
	cout<<"Positive"<<endl;
	else if(a<0&&b<0)
	{
		if((abs(a-b))%2==0)
		cout<<"Negative"<<endl;
		else 
		cout<<"Positive"<<endl;
	}
	else
	cout<<"Zero"<<endl;
	
	return 0;
	}

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

int main(){
	int N,D,ans=0;
	cin >> N >> D;
	int X[N][D];
	for(int i=0;i<N;i++)for(int j=0;j<D;j++)cin >> X[i][j];
	
	int sq[200];
	for(int i=0;i<200;i++)sq[i]=i*i;
	
	for(int i=0;i<N-1;i++)for(int j=i+1;j<N;j++){
		int dist=0;
		for(int d=0;d<D;d++)dist+=(X[i][d]-X[j][d])*(X[i][d]-X[j][d]);
		bool flag=false;
		for(int k=0;k<200;k++)if(dist==sq[k])flag=true;
		if(flag)ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;

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

    ll ans = b / x - (a - 1) / x;
    if (a == 0 && x >1)
    {
        ++ans;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3632
N = gets.chop.to_i
P = gets.chop.split(' ').map(&:to_s).join
Q = gets.chop.split(' ').map(&:to_s).join

# DFSで長さNの組み合わせを全検索実装

$n = (1..N).map(&:to_s)

def factorial(n)
  return 1 if n == 0
  return n * factorial(n - 1)
end

def dfs(ptns)
  stack = ['']
  max = factorial(N)

  until ptns.length == max
    str = stack.pop
    ptns << str if str.length == N

    unless str.length == N
      $n.each do |i|
        unless str.include?(i)
          stack << str + i
        end
      end
    end
  end

  return ptns
end

ptns = []

f = dfs(ptns)
f.sort!

pp = f.index(P)
qp = f.index(Q)

puts (pp - qp).abs


Measured memory_bytes: 4924
#include <stdio.h>

int main()
{
  int a,b,c,d,x,y;
  scanf("%d%d%d%d",&a,&b,&c,&d);
  x = c - a;
  y = d - b;
  printf("%d %d %d %d\n",c-y,d+x,a-y,b+x);
}


Measured memory_bytes: 128
N = int(input())

is_prime=[1]*(N+1) #is_prime[p]: pが素数か
n_factors = {}

for p in range(2,N+1):
  if is_prime[p] == 0:
    continue
  else:
    q = 2*p
    while q <=N:
      is_prime[q] = 0
      q+=p
    for n in range(p,N+1):
      while n%p ==0:
        n_factors[p] = n_factors.get(p,0) + 1
        n=n//p
#print(n_factors)
ans = 1
for f in n_factors.values():
  ans *= (f+1)
  ans %= 10**9+7
  
print(ans)
    

Measured memory_bytes: 3064
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

var (
	in= bufio.NewReader(os.Stdin)
	out= bufio.NewWriter(os.Stdout)
)

func main() {
	s := readString()

	switch s {
	case "Sunny":
		fmt.Println("Cloudy")
	case "Cloudy":
		fmt.Println("Rainy")
	case "Rainy":
		fmt.Println("Sunny")
	}
}

func readInt64Slice() []int64 {
	line := readStringSlice()
	slice := make([]int64, 0, len(line))
	for _, tmp := range line {
		val, err := strconv.ParseInt(tmp, 10, 64)
		if err != nil {
			fmt.Println(err)
			os.Exit(1)
		}
		slice = append(slice, val)
	}
	return slice
}
func readFloat64Slice() []float64 {
	line := readStringSlice()
	slice := make([]float64, 0, len(line))
	for _, tmp := range line {
		val, err := strconv.ParseFloat(tmp, 64)
		if err != nil {
			fmt.Println(err)
			os.Exit(1)
		}
		slice = append(slice, val)

	}
	return slice
}
func readString() string {
	s, _, _ := in.ReadLine()
	return string(s)
}
func readStringSlice() []string {
	line := readString()
	s := strings.Split(line, " ")
	return s
}
func dump(value ...interface{}) {
	for _, v := range value {
		fmt.Printf("%#v\n", v)
	}
}

Measured memory_bytes: 640
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <string>

using namespace std;

#define LL long long

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

int main() {
	int n, k;
	vector<int> a;
	int p;
	cin >> n >> k;
	for (int i = 0; i < n; ++i) {
		scanf("%d", &p);
		a.push_back(p);
	}
	int *s = new int[n + 1];
	s[0] = 0;
	for (int i = 1; i <= n; ++i) {
		s[i] = s[i - 1] + a[i - 1];
	}
	int res = 0;
	for (int i = k; i <= n; ++i) {
		if (s[i] - s[i - k] > res) {
			res = s[i] - s[i - k];
		}
	}
	printf("%.10lf\n", 0.5 * (res + k));
	return 0;
}

Measured memory_bytes: 1908
#include<stdio.h>
int main(void)
{
	int n,b;
	int a[10];
	int i,j,temp;
	char w[101];
	while (1) {
		scanf ("%d",&n);
		if (n==0)
		break;
		for (i=0;i<10;i++){
			a[i]=0;
		}
		b=0;
		j=0;
			scanf("%s",w);
			for(i=0;i<100;i++){
				j=j%n;
			if (w[i]=='L'){
				a[j]=a[j]+1+b;
				b=0;
			}
			else if(w[i]=='S'){
				b=b+a[j]+1;
				a[j]=0;
			}
			else {
				a[j]=a[j]+1;
			}
			j++;
			}
			for(i=1;i<n;i++){
				for(j=0;j<n;j++){
					if(a[j]>a[i]){
						temp=a[i];
						a[i]=a[j];
						a[j]=temp;
					}
				}
			}
		printf("%d",a[0]);
		for (i=1;i<n;i++){
			printf(" %d",a[i]);
		}
		printf (" %d\n",b);
	}
	return 0;
}

Measured memory_bytes: 604
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector> 
#include<limits>
#include<numeric>
#include<type_traits>
#include<math.h>
using namespace std;
typedef long long ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define in(x) cin >> x
#define out(str) cout << str << endl

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

int N,maxi=0,ans=0,pos=0;

int main(){
    cin>>N;
    int p[N];
    rep(i,N){
        cin>>p[i];
        if(maxi<=p[i]){
            maxi=p[i];
            pos=i;
        }
        ans+=p[i];
    }
    out(ans-p[pos]/2);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+5;
const int INF = 0x3f3f3f3f;

int a[N];

int main()
{     
    string s;
    cin >> s;
    int len = s.size();
    memset(a,0,sizeof(a));
    
	for(int i = 1;i <= len;++i) a[i] = s[len-i]-'0';
    
	int ans = 0;
	for(int i = 1;a[i] || i <= len;++i){
    	a[i+1] += a[i]/10;
    	a[i] %= 10;
		
		if(a[i] < 5) ans += a[i];
    	else if(a[i] > 5) ans += 10-a[i],a[i+1]++;
    	else{
    		if(a[i+1] >= 5) ans += 5,a[i+1]++;
    		else if(a[i+1] < 5) ans += 5;
		}
	}
	printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 5252
#include <bits/stdc++.h>
#define MAXN 100100
#define pii pair<int, int>
#define pb push_back
typedef long long ll;

using namespace std;

int n;
ll dp[MAXN][2], mod = 1e9 + 7;
vector<int> g[MAXN];

void dfs(int x, int p){
	dp[x][0] = 1;
	dp[x][1] = 1;
	for(auto i : g[x]){
		if(i == p) continue;
		dfs(i, x);
		dp[x][0] *= dp[i][1];
		dp[x][1] *= dp[i][0] + dp[i][1];
		dp[x][0] %= mod;
		dp[x][1] %= mod;
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    cin >> n;
    for(int i = 0; i < n - 1; i++){
    	int a, b;
    	cin >> a >> b;
    	g[a].pb(b);
    	g[b].pb(a);
    }
    dfs(1, -1);
    cout << (dp[1][0] + dp[1][1]) % mod;
}

Measured memory_bytes: 12928
//include <bits/stdc++.h>
#include <cstdio>
#include <algorithm>
#include <iostream>
#define rep(i,x,y) for (int i=x;i<=y;++i)

using namespace std;
const int N  =  3e5+23;

void read(int &x)
{
	int f=1;
	x=0;
	char ch=getchar();
	while (!isdigit(ch)) (ch=='-'?f=-1:0),ch=getchar();
	while ( isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return ;
}
int n;
char s[N];
int a1[N],a2[N];
int b1[N],b2[N];
int ans=233333333;
int main()
{
	read(n);
	scanf("%s",s+1);
	rep(i,1,n) 
	{
		a1[i]=a1[i-1];
		b1[i]=b1[i-1];
		if (s[i]=='E') a1[i]++;
		else b1[i]++;
	}
	for (int i=n;i>=1;--i) 
	{
		a2[i]=a2[i+1];
		b2[i]=b2[i+1];
		if (s[i]=='E') a2[i]++;
		else b2[i]++;
	}
	rep(i,0,n) ans=min(ans,b1[i-1]+a2[i+1]);
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 5248
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,K,*A = map(int,read().split())

dp = [0]*(K+K+1)
for n in range(K):
    if not dp[n]:
        for a in A:
            dp[n+a]=1

answer = 'First' if dp[K] else 'Second'
print(answer)


Measured memory_bytes: 4596
"""Boot-camp-for-Beginners_002_C_Rally_19-August-2020.py"""
import numpy as np
import sys

N=int(input())
X = list(map(int,input().split()))
s=0
for i in range(len(X)):
    s+=X[i]
P=int(s/N)

Sum_round_down=0
Sum_round_up=0
for i in range(len(X)):
    Sum_round_down+=(P-X[i])**2
    Sum_round_up+=(P+1-X[i])**2
if(Sum_round_down>=Sum_round_up):
    Sum=Sum_round_up
else:
    Sum=Sum=Sum_round_down
print(int(Sum))

Measured memory_bytes: 27004
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline LL read()
{
	LL f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int stack[20];
template<typename T>inline void write(T x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
template<typename T>inline void pr1(T x){write(x);putchar(' ');}
template<typename T>inline void pr2(T x){write(x);putchar('\n');}
LL a,b;
LL bin(int x){return 1LL<<x;}
LL query(LL l,LL r,int o)
{
	if(l>=r)return bin(o+1);
	return l+1+bin(o+1)-r;
}
LL solve(LL l,LL r)
{
	for(int i=60;i>=0;i--)if(r&bin(i))
	{
		if(l&bin(i))return solve(l-bin(i),r-bin(i));
		LL ret=bin(i)-l;int pre=-1;
		for(int j=i-1;j>=0;j--)if(r&bin(j)){pre=j;break;}
		if(pre==-1)return 2*ret+(l!=0);
		return ret+query(bin(pre+1)-1,l,i-1);
	}
	return 1;
}
int main()
{
	a=read();b=read();
	pr2(solve(a,b));
	return 0;
}


Measured memory_bytes: 128
from string import ascii_lowercase


def solve(s):
    if s[0] != 'A':
        return False
    ci = s.find('C')
    if not 2 <= ci <= len(s) - 2:
        return False
    exclude = [0, ci]
    for i, c in enumerate(s):
        if i in exclude:
            continue
        if c not in ascii_lowercase:
            return False
    return True


s = input()
print('AC' if solve(s) else 'WA')


Measured memory_bytes: 3772