akhauriyash/Code-Regression huggingface dataset:
#pragma region
#pragma GCC target("avx2")
#pragma GCC optimize("03")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std; typedef long double ld; typedef long long ll;
typedef unsigned long long ull;
#define endl "\n"
#define MP make_pair
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORR(x,arr) for(auto& x:arr)
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define VPII vector<PII>
#define VPLL vector<PLL>
#define FI first 
#define SE second
#define ALL(x) (x).begin(), (x).end()
constexpr int INF=1<<30; constexpr ll LINF=1LL<<60; constexpr ll mod=1e9+7; constexpr int NIL = -1;
template<class T>inline bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>inline bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
#pragma endregion
//-------------------

int main(){
    cin.tie(0); ios::sync_with_stdio(false); //cout << fixed << setprecision(15);
    int n; cin >> n;

    unordered_map<int, int> mp;
    for(int i=1; i*i<=n; i++) {
        for(int j=1; j*j<=n; j++) {
            for(int k=1; k*k <=n; k++) {
                int cur = i*i + j*j + k*k + i*j + j*k + k*i;
                mp[cur] ++;
            }
        }
    }
    FOR(i,1,n) {
        cout << mp[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 5084
import java.util.*;
public class Main {
	public static void main(String[] args) {
		A();
	}
	
	public static void A() {
		Scanner sc = new Scanner(System.in);
		Integer n = sc.nextInt();
		sc.close();
		String num = n.toString();
		if(num.charAt(1) != num.charAt(2)) {
			System.out.println("No");
			return;
		}
		char mid = num.charAt(1);
		if(mid == num.charAt(0) || mid == num.charAt(3)) {
			System.out.println("Yes");
		}
		else System.out.println("No");
	}
	
	
}


Measured memory_bytes: 23508
#include <bits/stdc++.h>
using namespace std;
using pint = pair<int,int>;

const long long INFLL = 1LL << 60;
const int INFI = 1000000000;

int main(){
    int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
    pint v;
    v.first = x2-x1; v.second = y2-y1;
    cout << x2-v.second << ' ' << y2+v.first << ' ';
    cout << x1-v.second << ' ' << y1+v.first << endl;
}


Measured memory_bytes: 256
A, B = map(int, input().split())
num_sum = (B - A) + 1
b_bin = format(B, 'b')
a_minus1_bin = format(A - 1, 'b').zfill(len(b_bin))

a_bin = a_minus1_bin[::-1]
b_bin = b_bin[::-1]

def cal(keta, maxi):
    q, mod = divmod(maxi, 2 ** keta)
    num_ones = q * (2 ** (keta - 1))

    s = mod - 2 ** (keta - 1)
    if s > 0:
        num_ones += s
    return num_ones

def cal_ones(keta):
    num_ones_b = cal(keta, B + 1)
    num_ones_a = cal(keta, A)
    return (num_ones_b - num_ones_a) % 2



str_ans = ""
for keta, (_a, _b) in enumerate(zip(a_bin, b_bin)):
    cur_str = cal_ones(keta + 1)
    str_ans += "{}".format(cur_str)

str_ans = str_ans[::-1]
print(int(str_ans, 2))

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

int main ()
{
  int S , W;
  scanf("%d %d",&S,&W);

  if (W>=S)printf("unsafe");
  else printf("safe");


 return 0;
}


Measured memory_bytes: 1736
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
typedef long long ll;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 200005;

int n, a[MAXN];
ll pri = LINF, c[MAXN];

int main(){
	scanf( "%d", &n );
	for( int i = 1; i <= n; ++i ){
		scanf( "%d", &a[i] );
		c[i] = c[i-1] + a[i];
	}
	for( int mid = 3; mid < n; ++mid ){
		ll a[4] = { 0, 0, 0, 0 };
		int L = 2, R = mid - 1;
		while( R - L > 5 ){
			int M = ( L + R ) >> 1;
			int LM = ( L + M ) >> 1;
			if( abs(c[mid-1]-2*c[M-1]) < abs(c[mid-1]-2*c[LM-1]) ) L = LM;
			else R = M;
		}
		int ans = L;
		for( ++L; L <= R; ++L ){
			// printf( "%lld %lld\n", abs(c[mid-1]-2*c[ans-1]), abs(c[mid-1]-2*c[L-1]) );
			if( abs(c[mid-1]-2*c[ans-1]) > abs(c[mid-1]-2*c[L-1]) )
				ans = L;
		}
		a[0] = c[ans-1]; a[1] = c[mid-1] - c[ans-1];
		L = mid + 1; R = n;
		while( R - L > 5 ){
			int M = ( L + R ) >> 1;
			int LM = ( L + M ) >> 1;
			if( abs(c[n]-2*c[M-1]+c[mid-1]) < abs(c[n]-2*c[LM-1]+c[mid-1]) ) L = LM;
			else R = M;
		}
		ans = L;
		for( ++L; L <= R; ++L )
			if( abs(c[n]-2*c[ans-1]+c[mid-1]) > abs(c[n]-2*c[L-1]+c[mid-1]) )
				ans = L;
		a[2] = c[ans-1] - c[mid-1]; a[3] = c[n] - c[ans-1];
		sort( a, a+4 );
		// printf( "%d %lld %lld %lld %lld\n", mid, a[0], a[1], a[2], a[3] );
		pri = min( pri, a[3] - a[0] );
	}
	printf( "%lld\n", pri );
	return 0;
}

Measured memory_bytes: 2560
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int>>
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define inf (1ll<<60)
#define Yes(f) cout<<(f?"Yes":"No")<<endl
#define yes(f) cout<<(f?"yes":"no")<<endl
#define YES(f) cout<<(f?"YES":"NO")<<endl
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v), greater<int>())

using namespace std;

const int mod=1e9+7;

void run();

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(12);
}

signed main(){
    init();
    run();
    return 0;
}

void run(){
    int n;
    cin>>n;
    vi a(n);
    rep(i,n)cin>>a[i];
    int g=a[0];
    Rep(i,1,n)g=__gcd(g,a[i]);
    cout<<g<<endl;
}

Measured memory_bytes: 1024
def main():
    cnt = 0
    for _ in range(m):
        x, y = map(int, input().split())
        unite(x, y)
    for i, pi in enumerate(p, 1):
        if same(i, pi):
            cnt += 1
    print(cnt)
        
def root(x):
    if parent[x] == x:
        return x
    parent[x] = root(parent[x])
    return parent[x]

def same(x, y):
    return root(x) == root(y)

def unite(x, y):
    x = root(x)
    y = root(y)
    if x != y:
        if rank[x] < rank[y]:
            parent[x] = y
        elif rank[x] > rank[y]:
            parent[y] = x
        else:
            parent[y] = x
            rank[x] += 1

if __name__ == "__main__":
    n, m = map(int, input().split())
    p = list(map(int, input().split()))
    parent = list(range(n+1))
    rank = [0]*(n+1)
    main()


Measured memory_bytes: 14452
package main
 
import(
  "fmt"
	"bufio"
	"os"
	"strings"
)
 
var sc = bufio.NewScanner(os.Stdin)
 
func Rr() []string {
  sc.Scan()
  slice := strings.Split(sc.Text(), " ")
  return slice
}
 
func solver(a int, b int){
	if a+b==3{
		fmt.Println(3)
	}else if a+b==4{
		fmt.Println(2)
	}else{
		fmt.Println(1)
	}
}
 
func main(){
	a := 0
	b := 0
	fmt.Scan(&a)
	fmt.Scan(&b)
	solver(a,b)
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define ll long long
#define _GLIBCXX_DEBUG
const ll MOD = 1000000007;
const int MAX = 510000;

long long f(string s) {
    int N = s.size();
    long long sum = 0;
    for (long long i = 0, j = 0; i < N; i = j) {
        while (j < N && s[i] == s[j])j++;
        sum += (j - i) / 2;
    }
    return sum;
}

int main() {

    string S;
    cin >> S;

    long long N = S.size();

    long long K;
    cin >> K;

    bool same = true;
    for (int i = 0; i < N; i++) if (S[0] != S[i]) same = false;
    if (same) {
        cout << (N * K) / 2 << endl;
        return 0;
    }

    long long d1 = f(S);
    long long d2 = f(S + S);

    long long a = d1;
    long long d = d2 - d1;

    cout << a + (K -1) * d << endl;

    return 0;
}



Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    private static final int MOD = 1_000_000_007;
    private static final String YES = "Yes";
    private static final String NO = "No";

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

        int N = sc.nextInt();
        int[] X = new int[N];
        for (int i=0; i<N; i++) {
            X[i] = sc.nextInt();
        }

        System.out.println(solve(N, X));
    }

    private static int solve(int N, int[] X) {
        int min = Integer.MAX_VALUE;

        for (int p=1; p<=100; p++) {
            int val = 0;
            for (int i=0; i<N; i++) {
                val += (int)Math.pow(X[i] - p, 2);
            }

            min = Math.min(min, val);
        }

        return min;
    }
}

Measured memory_bytes: 21844
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;

int main(){
  int h, w; cin >> h >> w;
  int c[h+1][w+1];
  //dp[i][j] means the length of maximum square using (i, j)
  int dp[h+1][w+1];
  int maxSq=0;
  for(int i=1;i<=h;i++){
    for(int j=1;j<=w;j++){
      cin >> c[i][j];
    }
  }
  //initialize dp
  for(int i=0;i<=h;i++) dp[i][0]=0;
  for(int i=0;i<=w;i++) dp[0][i]=0;
  for(int i=1;i<=h;i++){
    for(int j=1;j<=w;j++){
      if(c[i][j] == 1) dp[i][j]=0;
      else{
        dp[i][j]=min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]))+1;
        maxSq=max(maxSq, dp[i][j]);
      }
    }
  }
  cout << maxSq*maxSq << endl;
}

Measured memory_bytes: 18376
import java.util.*;

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

        int N = sc.nextInt();
        int D = sc.nextInt();
        int X = sc.nextInt();
        int[] A = new int[N];
        int sum = 0;

        for(int i=0; i<N; i++){
            A[i] = sc.nextInt();
        }

        for(int i=0; i<N; i++){
            for(int j=0; j<D; j++){
                if(j*A[i]+1<=D){
                    sum += 1;
                }
                else{
                    break;
                }
            }
        }
        System.out.println(sum + X);
    } 
}

Measured memory_bytes: 21844
square=['#','.']
while True:
  HW=input().split()
  HW=[int(x) for x in HW]
  if HW[0] == 0: break
  for i in range(HW[0]):
    for j in range(HW[1]):
      print(square[(i+1+j+1)%2], end='')
    print('')
  print('')

Measured memory_bytes: 7020
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <cmath>
#include <queue>
#include <numeric>
#include <climits>
#include <iterator>
#include <iomanip>
#include <stack>
#include <set>
#include <bitset>
#include <functional>
using namespace std;
const constexpr int INF = 1e9;
//typedef std::pair<std::string,double> P;


#define FOR(i, a, n) for (ll i = (ll)a; i<(ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

typedef long long ll;
typedef vector<int> VI;
const constexpr ll MOD = 1e9+7;
vector<pair<int, int> > vp;
 
struct Less {
    bool operator()(const pair<int, int>& x, const pair<int, int>& y) const {
        return x.first > y.first;
    }
};

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


//グラフの隣接リスト
VI g[200010];
//頂点の入次数を管理
int h[100010];

vector<int> v;
int a[501][501];
int main(void) {
    
    ll N, M, Q; cin >> N >> M >> Q;
    REP(i, M){
        int L, R; cin >> L >>R;
        a[L][R]++;
    }
    for(int i=1; i<=N; ++i){
        for(int j=1; j<=N; ++j){
            a[i][j]+=a[i][j-1];
        }
    }
    for(int j=1; j<=N; ++j){
        for(int i=1; i<=N; ++i){
            a[i][j]+=a[i-1][j];
        }
    }
    for(int i=0; i<Q; ++i){
        int p, q; cin >> p >> q;
        cout << a[q][q] + a[p-1][p-1] -a[p-1][q] - a[q][p-1] << endl;
    }
    return 0;
}

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

using namespace std;

int main()
{
    int n,x,t;
    cin>>n>>x>>t;
    if(n%x==0){
       int a=n/x*t;
       cout<<a; 
    }
    else{
        int a=n/x+1;
        cout<<a*t;
    }
    
}


Measured memory_bytes: 3612
def resolve():
    # 整数 1 つ
    # n = int(input())
    # 整数複数個
    w, h, n = list(map(int, input().split()))
    # 整数 N 個 (改行区切り)
    # N = [int(input()) for i in range(N)]
    # 整数 N 個 (スペース区切り)
    # N = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
#    P = [list(map(int, input().split())) for i in range(n)]

    Area = [[True] * w] * h
    for _ in range(n):
        x, y, a = list(map(int, input().split()))
        if a == 1:
            for i in range(h):
                for j in range(x):
                    Area[i][j] = False
        if a == 2:
            for i in range(h):
                for j in range(w - x):
                    Area[i][j + x] = False
        if a == 3:
            for i in range(y):
                Area[i] = [False] * w
        if a == 4:
            for i in range(h - y):
                Area[i + y] = [False] * w

    cnt = 0
    for i in Area:
        cnt += i.count(True)
    print(cnt)
resolve()

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

int main() {
  int N,count;
  cin>>N;
  count=0;
  vector<int>vec(N);
  for(int i=0;i<N;i++)cin>>vec.at(i);
  sort(vec.begin(),vec.end());
  for(int i=0;i<N-1;i++){
    if(vec.at(i)<vec.at(i+1))count++;
  }
  cout<<count+1<<endl;
    
}


Measured memory_bytes: 256
#include<iostream>

using namespace::std;

int  main(){
	int n;
  	cin>>n;
  	int ar[n],sum=0;
  	for(int i=0;i<n;i++)
      cin>>ar[i],sum+=ar[i];
  	int m;
  	cin>>m;
  	for(int j=0,l,r;j<m;j++){
      cin>>l>>r;
      cout<<sum+r-ar[l-1]<<'\n';
    }
}

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

using ll = long long;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i < (n); i++)
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}

int main()
{
    double A, B, H, M; cin >> A >> B >> H >> M;
    
    double x = 6 * M;
    double y = 30 * H + 0.5 * M;
    double deg = min(abs(x-y), abs(y-x));

    double ans = sqrt(A*A + B*B - 2 * A * B * cos(M_PI * deg/180.0));
    cout << fixed << setprecision(15);
    cout << ans << endl;
}


Measured memory_bytes: 4216
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = s; i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << '\n';
#define CFYN(n) cout << ( (n) ? "YES":"NO") << '\n';
#define OUT(n) cout << (n) << '\n';
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

int main(void)
{
    IOS
    int a, b;
    cin >> a >> b;
    if (a + b < 10) OUT(a+b)
    else OUT("error")

    return 0;
}

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

int main() {
  string s, t;
  cin >> s >> t;

  int r = 1e9;
  for (int i = 0; i + t.size() <= s.size(); i++) {
    int ri = 0;
    for (int j = 0; j < t.size(); j++) {
      if (s[i + j] != t[j]) ri++;
    }
    r = min(r, ri);
  }
  cout << r << endl;
}


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

//{{{
/********************************************************************/
struct Fast {Fast(){std::cin.tie(0);ios::sync_with_stdio(false);}} fast;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vii;
typedef queue<int> qi;
typedef stack<int> si;
typedef deque<int> dqi;

#define reps(i, a, b) for (int i = a; i < b; ++i)
#define rep(i, n) reps(i, 0, n)
#define REPS(i, a, b) reps(i, a, b)
#define REP(i, n) rep(i, n)
#define deps(i, a, b) for (int i = a; i >= b; --i)
#define dep(i, n) deps(i, n, 0)
#define DEPS(i, a, b) deps(i, a, b)
#define DEP(i, n) dep(i, n)

#define pf push_front
#define pb push_back
#define mp make_pair
#define fst first
#define FST fst
#define sec second
#define SEC sec
#define sz(obj) ((int)(obj).size())
#define all(v) (v).begin(), (v).end()
#define ALL(v) all(v)

const int INF = 999999999;
const int MOD = 1e9 + 7;
const int dx[] = {0, 1, 0, -1, 1, 1, -1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

vector<string> split(const string &s, char delim) {
  vector<string> elems;
  string item;
  for (char ch: s) {
    if (ch == delim) {
      if (!item.empty()) elems.push_back(item);
      item.clear();
    }
    else item += ch;
  }
  if (!item.empty()) elems.push_back(item);
  return elems;
}

inline bool inside(int y, int x, int H, int W) {return y >= 0 && x >= 0 && y < H && x < W;}
inline int in() {int x; std::cin >> x; return x;}
template <typename T>
void print(std::vector<T>& v, char c = ' ') {
  REP(i, v.size()) {
    if (i != 0) std::cout << c;
    std::cout << v[i];
  }
  std::cout << endl;
}
template <typename T> void print(T x) { std::cout << x << '\n'; }

/****************************************************************/
//}}}

signed main()
{
  string str;
  int n, cnt = 0;
  cin >> str >> n;
  int len = sz(str);

  rep(i, n) {
    string s;
    bool flg = false;
    cin >> s;
    s += s;
    reps(j, len, sz(s)) {
      if (str == s.substr(j - len, len)) flg = true;
    }
    if (flg) cnt++;
  }
  print(cnt);

  return (0);
}

Measured memory_bytes: 3212
#include<iostream>
using namespace std;
int main()
{
	int n,a,b,ans=0,temp,tempsum;
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++){
		temp=i;
		tempsum=0;
		while(temp>=10){
			tempsum+=temp%10;
			temp/=10;
		}
		tempsum+=temp;
		if(tempsum>=a&&tempsum<=b){
			ans+=i;
		}
	}
	cout<<ans<<endl;
}

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

int main()
{
    string str;
    cin>>str;
    int n=str.size()-1;
 
    long long int ans=0;
    long long int temp=0;

    for (int bit =0;bit<(1<<n);++bit)
    {
        string strc=str;
        for (int i=0;i<n;++i)
        {
            if(bit&(1<<i))
            {
                strc.insert(n-i,"+");
            }
        }
   
        for (char j:strc)
        {
            if(j=='+')
            {
                ans+=temp;
                temp=0;
            }
            else
            {
                temp=temp*10+j-'0';
            }
        }
        ans+=temp;
        temp=0;
    }
    cout<<ans<<endl;
}



Measured memory_bytes: 3628
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

s=set()
data=[1,7,9,4]
for si in map(int,input().split()):
    if si in data:
        s.add(si)
print("YES" if len(s)==4 else "NO")

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

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

  int a[N];
  bool pos = false;
  rep(i,0,N-1) {
    cin >> a[i];
    if (a[i] == 2) pos = true;
  }

  int ans = -1;
  if (pos) {
    int i = 0;
    set<int> s;
    ans = 0;
    while (1) {
      ans++;
      i = a[i] - 1;
      if (s.count(i) != 0) {
        ans = -1;
        break;
      }
      s.insert(i);
      if (i == 1) break;
    };
  }

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


Measured memory_bytes: 5376
N, K = map(int, input().split())

ans = 0

def calc(x, goal):
    res = 0
    while x < goal:
        x *= 2
        res += 1
    return res    


for i in range(1, N+1):
    cnt = calc(i, K)
    ans += 1 / N * ((1 / 2) ** cnt)

print(ans)

Measured memory_bytes: 72088
import java.util.Scanner;

//UTF-8
public class Main{

	String[][] p = {{"0xxxxxxx"}, 
			{"110yyyyx", "10xxxxxx"},
			{"1110yyyy", "10yxxxxx", "10xxxxxx"},
			{"11110yyy", "10yyxxxx", "10xxxxxx", "10xxxxxx"}
	};

	void run(){
		Scanner sc = new Scanner(System.in);
		int MOD = 1000000;
		for(;;){
			int n = sc.nextInt();
			if(n==0)break;
			char[][] s = new char[n][8];
			for(int i=0;i<n;i++)s[i]=sc.next().toCharArray();
			long[][] dp = new long[n+1][4];
			dp[n][0] = 1;
			for(int i=n-1;i>=0;i--)for(int L=0;L<4;L++){
				if(n<=i+L)continue;
				boolean ok = true;
				int ys = 0, xs = 0, y1 = 0;
				for(int j=0;j<=L;j++)for(int k=0;k<8;k++){
					char ch = p[L][j].charAt(k);
					if(ch=='0'){
						if(s[i+j][k]=='1')ok = false;
					}
					if(ch=='1'){
						if(s[i+j][k]=='0')ok = false;
					}
					if(ch=='x'){
						if(s[i+j][k]=='x')xs++;
					}
					if(ch=='y'){
						if(s[i+j][k]=='1')y1++;
						if(s[i+j][k]=='x')ys++;
					}
				}
				if(ok){
					long res = (1L<<xs)%MOD;
					if(0<L){
						if(y1==0){
							res = (res*((1<<ys)-1))%MOD;
						}
						else{
							res = (res*(1<<ys))%MOD;
						}
					}
					for(int j=0;j<4;j++){
						dp[i][L] = (dp[i][L]+res*dp[i+L+1][j])%MOD;
					}
				}
				else dp[i][L] = 0;
			}
			long res = 0;
			for(int j=0;j<4;j++)res+=dp[0][j];
			System.out.println(res%MOD);
		}
	}

	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 12000
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <stack>
#include <vector>
#include <set>
#include <tuple>
#include <utility>
#include <functional>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
const int INF = 1000000000;
const int MOD = 1000000007;

int main(){
	int a[4];
	string s;
	cin >> s;
	for(int i = 0;i < 4;i++)a[i] = s[i] - '0';
	for(int i = 0;i < (1 << 3);i++){
		string emp = to_string(a[0]);
		int now = a[0];
		for(int j = 0;j < 3;j++){
			if((i >> j) & 1){
				emp += '+';
				emp += '0' + a[j+1];
				now += a[j+1];
			}
			else{
				emp += "-";
				emp += '0' + a[j+1];
				now -= a[j+1];
			}
		}

		if(now == 7){
			cout << emp+"=7" << endl;
			return 0;
		}
	}
}


Measured memory_bytes: 256
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        n: usize,
        mut p: [usize; n],
    }

    let mut count = 0;
    for i in 0..p.len() - 1 {
        if p[i] != (i + 1) {
            continue;
        };
        count += 1;
        p[i + 1] = p[i];
    }
    if p[p.len() - 1] == p.len() {
        count += 1;
    }

    println!("{}", count);
}


Measured memory_bytes: 3288
#include<stdio.h>
int max(int a, int b) {
	if (a >= b) return a;
	return b;
}
int main() {
	int a, b, n, i;
	a = 0; b = 0;
	for (i = 0; i < 4; i ++) {
		scanf("%d", &n); a += n;
	}
	for (i = 0; i < 4; i ++) {
		scanf("%d", &n); b += n;
	}
	printf("%d\n", max(a, b));
	return 0;
}

Measured memory_bytes: 592
while 1:
    d, w = map(int, input().split())
    if d == w == 0:
        break
    E = [0]*d
    for i in range(d):
        *E[i], = map(int, input().split())
    ans = 0
    for x2 in range(d):
        for y2 in range(w):
            for x1 in range(x2-1):
                for y1 in range(y2-1):
                    co = 10**18
                    for x in range(x1, x2+1):
                        co = min(co, E[x][y1], E[x][y2])
                    for y in range(y1, y2+1):
                        co = min(co, E[x1][y], E[x2][y])
                    ci = cnt = 0
                    for x in range(x1+1, x2):
                        for y in range(y1+1, y2):
                            ci = max(ci, E[x][y])
                            cnt += E[x][y]
                    if ci < co:
                        ans = max(ans, (x2-x1-1)*(y2-y1-1)*co - cnt)
    print(ans)

Measured memory_bytes: 7664
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int, int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int;
int dx[8] = { 1, 0, -1, 0, 1, -1, -1, 1 };
int dy[8] = { 0, 1, 0, -1, 1, 1, -1, -1 };
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; }
struct io { io() { ios::sync_with_stdio(false); cin.tie(0); } };
const int INF = INT_MAX;
const ll LLINF = 1LL << 60;
const ll MOD = 1000000007;
const double EPS = 1e-9;
//#include <math.h>
int main(void) 
{
    ll n;
    cin>> n;
    vll a(n);
    
    
    rep(i, n) {
        cin >>a[i];
    }
    Sort (a);
    
    rrep (i, n-1) {
        if (a[i] == a[i-1]) {
            cout <<"NO";
            return 0;
        }
    }
    
    
    cout << "YES";
    
    return 0;
}

Measured memory_bytes: 4844
// in the name if Allah
#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
const ll INF = 1<<30 ;
const ll N= 1e6 ;
#define f first
#define s second
ll n , k , mod = 1000000007 , c[2010][2010];
vector<char> v ;
ll poww(ll a , ll b){
if(b==0)return 1 ;
ll x = poww(a , b/2)%mod ;
x %= mod ;
if(b&1)return (((x*x)%mod)*a)%mod ;
else return (x*x)%mod ;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> k ;
for(int i = 0 ; i <= 2001 ; i ++){c[i][0] = 1 ; c[i][i] = 1 ; c[i][1] = i ; }
for(int i = 2 ; i <= 2001 ; i ++){
    for(int j = 1 ; j < i ; j++)c[i][j] = (c[i-1][j] + c[i-1][j-1])%mod  ;
}
for(int i = 1 ; i<= k ; i ++){
    ll x1 = c[n-k+1][i] %mod  , x2 = c[k-1][i-1] %mod ;
    cout << (x1*x2)%mod << endl ;
}
    return 0;
}
 /*
              _     _   __
        /_\  (_    (_)  __)
       /   \  _) . (_) (__
 */


Measured memory_bytes: 30208
#include <iostream>

int main(int argc, char const *argv[]) {
  char c[2] = {'#','.'};
  while(1){
    int height=0,width=0;
    std::cin >> height >> width;
    if((height==0)&&(width==0))break;
    for(int i=0;i<height;i++){
      for(int j=0;j<width;j++){
        std::cout << c[(i+j)%2];
      }
      std::cout << std::endl;
    }
    std::cout << std::endl;
  }
  return 0;
}

Measured memory_bytes: 3108
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <utility>
#include <climits>
#include <string>
#include <tuple>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int INF=1<<29;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,m,Ans=0;
	cin>>n>>m;
	vector<int> k(m),p(m);
	vector<vector<int>> s(m);
	for(int i=0;i<m;i++){
		cin>>k[i];
		for(int j=0;j<k[i];j++){
			int tmp;
			cin>>tmp;
			s[i].push_back(tmp);
		}
	}
	for(int i=0;i<m;i++) cin>>p[i];
    for(int bit=0;bit<(1<<n);bit++){
		vector<bool> lamp(n);
        for(int i=0;i<n;i++){
            if(bit&(1<<i)){
				lamp[i]=true;
			}else{
				lamp[i]=false;
			}
        }
		for(int i=0;i<m;i++){
			int c=0;
			for(int j=0;j<s[i].size();j++){
				if(lamp[s[i][j]-1]) c++;
			}
			if(c%2==p[i]) continue;
			else goto Exit;
		}
		Ans++;
		Exit:;
    }
	cout<<Ans<<endl;
	return 0;
}


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

using namespace std;
const int N = 100001;
int n;
vector<vector<int> > adjList(N);


int solve(int node) {
    vector<int> vec;
    for(int ch : adjList[node])
        vec.push_back(solve(ch));
    sort(vec.begin(),vec.end());
    int cnt = 0;
    for(int i = 0;i<vec.size();i++) {
        if(vec[i] <= cnt)
            cnt++;
        else
            cnt = vec[i]+1;
    }
    return cnt;
}

int main()
{
    scanf("%d",&n);
    for(int i = 2;i<=n;i++) {
        int x;
        scanf("%d",&x);
        adjList[x].push_back(i);
    }
    printf("%d",solve(1));
    return 0;
}


Measured memory_bytes: 13568
N, M = map(int, input().split())
xys = [list(map(int, input().split())) for _  in range(M)]

children = [[] for _ in range(N)]
for x, y in xys:
    children[x-1].append(y-1)

has_no_parent = [True] * N
has_no_child = [True] * N
for x, y in xys:
    has_no_child[x-1] = False
    has_no_parent[y-1] = False

dp = [None] * N
for node in range(N):
    if has_no_child[node]:
        dp[node] = 0

for node in range(N):
    if dp[node] is not None:
        continue
    stack = []
    stack.append(node)
    while stack:
        parent = stack[-1]
        all_children_defined = True
        for child in children[parent]:
            if dp[child] is None:
                stack.append(child)
                all_children_defined = False
        if all_children_defined:
            stack.pop()
            dp[parent] = max([dp[child] + 1 for child in children[parent]])

print(max(dp))


Measured memory_bytes: 43348
#include <bits/stdc++.h>
#define int long long
#define double long double
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define ms(v,x) memset(v,x,sizeof(v))
#define ff first
#define ss second
#define frr(i,n) for(int i=0;i<n;i++)
#define td(v) v.begin(),v.end()
#define M   1000000007 // 1e9 + 7
#define MAXN 200100
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,double> pdd;
inline int mod(int n, int m){int ret = n%m; if(ret < 0) ret += m; return ret;}
int gcd(int a, int b){return (b == 0 ? a : gcd(b, a%b));}
int exp(int a,int b,int m){
    if(b==0) return 1;
    if(b==1) return mod(a,m);
    int k = mod(exp(a,b/2,m),m);
    if(b&1){
        return mod(a*mod(k*k,m),m);
    }    else return mod(k*k,m);
}

int ok[30];
#define PI 3.14159265

int k;

int F[MAXN];
int A[MAXN];

int32_t main(){
	fastio;
	int a,b,x;
	cin>>a>>b>>x;
	if(2*x>=a*a*b){
		double v1 =  (a*a*b - x)*2.0;
		v1 = v1/(1.0*a*a*a);
		
		double tang = atan(v1)*180.0/PI;		
		cout<<setprecision(7)<<fixed;
		cout<<tang<<endl;
	}else{
		double v1 = (1.0*b*b*a)/(2.0*x);
		double tang = atan(v1)*180.0/PI;
		cout<<setprecision(7)<<fixed;
		cout<<tang<<endl;	
		
	}
	
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x)          (x).begin(), (x).end()
#define rep(i, n)       for (i64 i = 0, i##_limit = (n); i < i##_limit; ++i)
#define reps(i, s, t)   for (i64 i = (s), i##_limit = (t); i <= i##_limit; ++i)
#define repr(i, s, t)   for (i64 i = (s), i##_limit = (t); i >= i##_limit; --i)
#define var(Type, ...)  Type __VA_ARGS__; input(__VA_ARGS__)
#ifndef DBG
#define trace(...)
#endif
using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class T, class U> inline bool chmax(T &a, const U &b) { return b > a && (a = b, true); }
template <class T, class U> inline bool chmin(T &a, const U &b) { return b < a && (a = b, true); }
inline i64  sigma(i64 n)            { return (n * (n + 1) >> 1); }
inline i64  updiv(i64 a, i64 b)     { return (a + b - 1) / b; }
inline i64  sqr(i64 n)              { return n * n; }
inline string to_string(char c)     { return string(1, c); }
constexpr int INF  = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

template <class T>
inline vector<T> make_v(const T &initValue, size_t sz) {
    return vector<T>(sz, initValue);
}
template <class T, class... Args>
inline auto make_v(const T &initValue, size_t sz, Args... args) {
    return vector<decltype(make_v<T>(initValue, args...))>(sz, make_v<T>(initValue, args...));
}

inline void input() {}
template <class Head, class... Tail>
inline void input(Head &head, Tail&... tail) { cin >> head; input(tail...); }

inline void print() { cout << "\n"; }
template <class Head, class... Tail>
inline void print(Head &&head, Tail&&... tail) {
    cout << head;
    if (sizeof...(tail)) cout << ' ';
    print(forward<Tail>(tail)...);
}

template <class T>
inline ostream& operator<< (ostream &out, const vector<T> &vec) {
    static constexpr const char *delim[] = { " ", "" };
    for (const auto &e : vec) out << e << delim[&e == &vec.back()];
    return out;
}

template <typename Func>
struct FixPoint : Func {
    inline constexpr FixPoint(Func &&f) noexcept : Func(forward<Func>(f)) {}

    template <typename... Args>
    inline decltype(auto) operator()(Args &&... args) const {
        return Func::operator()(*this, forward<Args>(args)...);
    }
};

template< typename Func >
inline decltype(auto) makeFixPoint(Func &&f) {
    return FixPoint< Func >{forward< Func >(f)};
}
// }}} End Header

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

    var(int, a, b);
    if (a < 1 || a > 9 || b < 1 || b > 9) print(-1);
    else print(a * b);

    return 0;
}


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

int main(){

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

    sort(a.begin(), a.end());

    for(int i = 0; i < N; i++){
        if(x - a[i] == 0){
            cout << i + 1 << endl;
            return 0;
        }else if(x - a[i] < 0){
            cout << i << endl;
            return 0;
        }
        x -= a[i];
    }

    cout << N - 1 << endl;

    return 0;
}

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

using namespace std;

int N, K, A[100000];
vector< int > g[100000];
int depth[100000];
int rec(int idx)
{
  int ret = 0;
  for(int to : g[idx]) {
    ret += rec(to);
    depth[idx] = max(depth[idx], depth[to] + 1);
  }
  if(depth[idx] == K - 1 && idx != 0 && A[idx] != 0) {
    depth[idx] = -1;
    ++ret;
  }
  return(ret);
}

void Calculation()
{
  cin >> N >> K;
  for(int i = 0; i < N; i++) {
    cin >> A[i];
    --A[i];
    if(i) g[A[i]].push_back(i);
  }
  cout << rec(0) + (A[0] != 0) << endl;
}

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

Measured memory_bytes: 12800
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
#define endl '\n'
#define fi first
#define se second
#define pi pair<ll,ll>
#define pii pair<ll,pi>
#define pb push_back
#define mk make_pair
int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n;
	cin >> n;
	vector<ll>v(n);
	const ll nax = 1e6 + 7;
	vector<ll>sieve(nax, 0);
	ll g = v[0];
	for (ll i = 0; i < n; i++) {
		cin >> v[i];
		sieve[v[i]]++;
		if (i >= 1)
			g = __gcd(g, v[i]);
	}
	int ans = 0;
	bool ok = false;
	for (ll i = 2; i < nax; i++) {
		ll cnt = 0;
		for (ll j = i; j < nax; j += i) {
			cnt += sieve[j];
		}
		if (cnt >= 2)
			ok = true;
		if (cnt >= n)
			ans++;
	}
	if (ans >= 1 && g != 1)
		cout << "not coprime" << endl;
	else {
		if (ans == 0 && ok)
			cout << "setwise coprime" << endl;
		else
			cout << "pairwise coprime" << endl;
	}
}

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

#define debug(x) cout <<"DEBUG"<<" "<< #x << ":" << x << '\n'

//↓0-originか1-originでn回繰り返し
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   //0-origin昇順
#define rep1(i,n) for(int i = 1; i <= ((int)(n)); i++) //1-origin昇順
#define rrep(i,n) for(int i = ((int)(n)-1); i >= 0; i--)  //0-origin降順
#define rrep1(i,n) for(int i = ((int)(n)); i >= 1; i--)   //1-origin降順
//rep2 -> 第二引数 m から n 回繰り返し ex) m=5 n=3 なら i=5,i=6,i=7 まで
#define rep2(i,m,n) for(int i = ((int)(m)); i < ((int)(n))+((int)(m)); i++)
#define SIZE(x) ((int)((x).size()))
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vii; //2次元配列
typedef vector<ll> vll;
typedef vector<string> vs;
typedef pair<int, int> PII;
template<class T,class U> inline bool chmax(T &a, const U &b){if(a<b){a=b;return 1;}return 0;}
template<class T,class U> inline bool chmin(T &a, const U &b){if(a>b){a=b;return 1;}return 0;}

/* 円周率は M_PI を使おうね */
const ll infll = (1LL<<62)-1;
const int inf = (1<<30)-1;
int mod = 1000000007;

/*FUNCs=================================================*/
vi move1 = {0,0,1,-1};
vi move2 = {1,-1,0,0};
/*prime_test=================================================*/
bool prime_test(int num) {
    if (num < 2) return false;           // 0 と 1 除く
    else if (num == 2) return true;      //2はtrue
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

    int sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2){
        if (num % i == 0) return false;  // 素数ではない
    }
    // 素数である
    return true;
}
/*============================================================*/
/*MAIN==================================================*/
signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);   //cin cout 高速化
    //cout << fixed << setprecision(10);

    ll n, k, r,s,p; cin >> n >> k >> r >>s >> p;
    ll ans = 0;
    string t; cin >> t;
    string st;
    for(int i = 0; i < k; ++i) {
        if(t[i]=='r') {
            ans += p;
            st.push_back('p');
        }
        else if(t[i]=='s') {
            ans += r;
            st.push_back('r');
        }
        else if(t[i]=='p'){
            ans += s;
            st.push_back('s');
        }
    }
    for(int i = k; i < n; ++i) {
        if(t[i]=='r') {
            if(st[i-k]=='p') st.push_back('x');
            else {
                ans += p;
                st.push_back('p');
            }
        }
        if(t[i]=='s') {
            if(st[i-k]=='r') st.push_back('x');
            else {
                ans += r;
                st.push_back('r');
            }
        }
        if(t[i]=='p') {
            if(st[i-k]=='s') st.push_back('x');
            else {
                ans += s;
                st.push_back('s');
            }
        }
    }
    cout << ans << '\n';
}


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

int main()
{
    long long n,c=0,ans = 0;
    cin>> n;
    for(int i=0;i<1e7;i++)
    {
        c+=7;
        c%=n;
        c*=10;
        ans+=1;
        if(c==0)
            break;
    }
    if(c==0)
        cout<<ans;
    else
        cout<<-1;
}


Measured memory_bytes: 3668
#include<bits/stdc++.h>                                                                                                                                                                                     
using namespace std;
int main(){
  int N,i,j,count=0;
  cin >> N;
  vector<int> d(N);
  for(i=0; i<N; i++)
    cin >> d.at(i);
  for(i=0; i<N; i++){
    for(j=0; j<N; j++){
      if(i!=j && d.at(i)==d.at(j))
        d.at(j)=0;
    }
  }
  for(i=0; i<N; i++){
    if(d.at(i)!=0)
      count++;
  }
  cout << count << endl;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
n, m = map(int, input().split())
a = set([int(input()) for _ in range(m)])

INF = 1000000007

dp = [0] * (n+1)
dp[0] = 1

if 1 not in a:
    dp[1] = 1
else:
    dp[1] = 0

for i in range(2, n+1):
    if i in a:
        continue
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= INF

print(dp[n])


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

int main() {
	long long n, a, b; cin >> n >> a >> b;
	if (a > b) { cout << 0 << endl; return 0; }
	if (n == 1) {
		if (a != b) { cout << 0 << endl; return 0; }
		else { cout << 1 << endl; return 0; }
	}

	long long ans = ((n - 1) * b + a) - ((n - 1) * a + b) + 1;
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
h,w,k = map(int, input().split())
cake = [input() for i in range(h)]
ans = [[0]*w for i in range(h)]

now = 1
for i in range(h):
    for j in range(w):
        if cake[i][j] == '#':
            ans[i][j] = now
            now+=1

for i in range(h):
    for j in range(1,w):
        if ans[i][j] == 0:
            ans[i][j] = ans[i][j-1]

for i in range(h):
    for j in reversed(range(w-1)):
        if ans[i][j] == 0:
            ans[i][j] = ans[i][j+1]

for i in range(1,h):
    for j in range(w):
        if ans[i][j] == 0:
            ans[i][j] = ans[i-1][j]

for i in reversed(range(h-1)):
    for j in range(w):
        if ans[i][j] == 0:
            ans[i][j] = ans[i+1][j]

for i in range(h):
    for j in range(w):
        print(ans[i][j], end=' ')
    print()

Measured memory_bytes: 7568
#include <stdio.h>

int main(void) {
	int a, b, c, d, e, k;
	scanf("%d%d%d%d%d%d", &a, &b, &c, &d, &e,&k);
	if (b - a <= k) {
		if (c - a <= k) {
			if (d - a <= k) {
				if (e - a <= k) {
					if (c - b <= k) {
						if (d - b <= k) {
							if (e - b <= k) {
								if (d - c <= k) {
									if (e - c <= k) {
										if (e - d <= k) {
											printf("Yay!\n");
											return 0;
										}
									}
								}
							}
						}
					}
				}
			}
		}
	}
	printf(":(\n");
	return 0;
}

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

int d,t,s;

inline int qr()
{
	char a=0;int x=0,w=1;
	while(a<'0'||a>'9'){if(a=='-')w=-1;a=getchar();}
	while(a<='9'&&a>='0'){x=(x<<1)+(x<<3)+(a^48);a=getchar();}
	return x*w;
}

int main()
{
	d=qr();
	t=qr();
	s=qr();
	int k;
	if(d%s==0)
		k=d/s;
	else
		k=d/s+1;
	if(k>t)
		cout<<"No"<<endl;
	else
		cout<<"Yes"<<endl;
	return 0;
}

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

void print(int left,int sum,string res){
        if(sum == 0){
                res.pop_back();
                std::cout<<res<<std::endl;
        }
        for(int i = min(left,sum);i >= 1; i--){
                print(i,sum - i,res + std::to_string(i) + " ");
        }
}

int main(){
        while(1){
        int n;
        cin>>n;
        if(!n)break;
        print(31,n,"");
        }
}

Measured memory_bytes: 3220
#include <iostream>
#include <cstring>
#include <map>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#include <list>
#include <numeric>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <math.h>
#include <stack>
#include <climits>
#include <bitset>

using namespace std;
typedef long long ll;

//最小公倍数
ll gcd(ll x, ll y) {
  ll tmp = 0;
  if (x < y){
    tmp=x;
    x=y;
    y=tmp;
  }
  while (y > 0) {
    ll r = x % y;
    x = y;
    y = r;
  }
  return x;
}

//最大公倍数
ll lcm(ll x,ll y){
  return x/gcd(x,y)*y;
}

//階乗
ll kaijo(ll k){
    ll sum = 1;
    for (ll i = 1; i <= k; ++i)
    {
        sum *= i;
        sum%=1000000000+7;
    }
    return sum;
}

//for(int i = ; i < ; i++){}

int main(){
  int n,d;
  cin>>n>>d;
  int sum = 0;
  int k = 0;
  while(sum  < n){
    k++;
    sum+=2*d+1;
  }
  cout<<k<<endl;
  return 0;
}

  



Measured memory_bytes: 256
def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    INF = 10**9

    H, W, K = map(int, input().split())
    chocolate = [ input()[:-1] for _ in range(H) ]
    
    loop_H = range(H)
    loop_W = range(W)
    min_cut = INF-1
    for div in range(1 << (H-1)):
        # 横割りでグループ分け
        group = [[]]
        group_number = 0
        for i in loop_H:
            group[group_number].append(i)
            if div >> i & 1:
                group.append([])
                group_number += 1
        # 縦に切っていく
        cut = group_number
        zeros = [0] * len(group)
        cnt = zeros.copy()
        w = 0
        while w < W:
            now = zeros.copy()
            for g in range(len(group)):
                for i in group[g]:
                    if chocolate[i][w] == '1':
                        now[g] += 1
                if now[g] > K:
                    cut = INF
                    break
                if cnt[g] + now[g] > K:
                    cut += 1
                    w -= 1
                    cnt = zeros.copy()
                    break
                cnt[g] += now[g]
            w += 1
        if cut < min_cut:
            min_cut = cut
    print(min_cut)

main()

Measured memory_bytes: 3064
n = int(input())
a = list(map(int, input().split()))

uv = [[] for _ in range(n)]
for _ in range(n-1):
    i, j = map(int, input().split())
    uv[i-1].append(j-1)
    uv[j-1].append(i-1)

# DFS
# 頂点iが未探索の時、ans[i] = -1
ans = [-1 for _ in range(n)]
ans[0] = 1
# dp[i] = 長さi+1のLISの最後尾の最小値
dp = [a[0]]
# history[(i, j)]のとき、変更前はdp[i] = j
# stackとして使用
history = []
# 頂点parents[i] = iの親
parents = [-1 for _ in range(n)]

todo = []
for i in uv[0]:
    todo.append(i)
    parents[i] = 0

while True:
    i = todo.pop(-1)
    
    # ans[i]を求める
    if dp[-1] < a[i]:
        dp.append(a[i])
        history.append((-1, 0))
    else:
        # dpの変更点を二分探索
        start = 0
        stop = len(dp) - 1
        flag = True
        while start < stop:
            center = (start + stop) // 2
            if dp[center] < a[i]:
                start = center + 1
            elif dp[center] > a[i]:
                stop = center
            else:
                flag = False
                break
        if flag and dp[start] > a[i]:
            history.append((start, dp[start]))
            dp[start] = a[i]
        else:
            history.append((-2, 0))
    ans[i] = len(dp)

    # todoに追加
    for j in uv[i]:
        if ans[j] == -1:
            todo.append(j)
            parents[j] = i

    if len(todo) == 0:
        break

    # back
    j = i
    while parents[todo[-1]] != j:
        k = history.pop(-1)
        if k[0] == -2:
            None
        elif k[0] == -1:
            dp.pop(-1)
        else:
            dp[k[0]] = k[1]
        j = parents[j]

for i in ans:
    print(i)

Measured memory_bytes: 68088
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
 
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("-ffloat-store")
 
#define int  long long
#define rep(i,begin,end) for(__typeof(end)i=(begin)-((begin)>(end));i!=(end)-((begin)>(end));i+=1-2*((begin)>(end)))
#define F first
#define S second
#define sz(x) ((int)x.size())
#define pb push_back
#define pf push_front
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define mod 1000000007
#define what_is(x) cerr << #x << " is " << x <<"\n";
#define sortA(v) sort(v.begin(), v.end())
#define sortD(v) sort(v.rbegin(), v.rend())
#define PI 3.14159265358979323846
#define vout(a) for(auto x:a) cout<<x<<" ";
#define INF 10000000000000000 //1e16
 
// #define ordered_set tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
 
 
// using namespace __gnu_pbds;
using namespace std;
 
using ll  = long long;
using vi  = vector<int>;
using pii = pair<int,int>;
using vii = vector<pii>;
using mi  = multiset<int>;
using mii = multiset<pii>;
 
int lcm(int a,int b) {return (a*(b/__gcd(a,b)));}



void solve()
{
    int t,n,m,i,k,r,l,u,v,w,j,s,sum=0,pos,flag=0,count=0;
    string S,T,U; 
    // int a,b,c;
    cin>>n;
    map<string,int> occ;
    rep(i,0,n)
    {
        cin>>S;
        occ[S]++;
    }
    cout<<"AC x "<<occ["AC"]<<"\n";
    cout<<"WA x "<<occ["WA"]<<"\n";
    cout<<"TLE x "<<occ["TLE"]<<"\n";
    cout<<"RE x "<<occ["RE"]<<"\n";
}
 
 
signed main()
{
    #ifndef ONLINE_JUDGE 
       freopen("input.txt","r",stdin);
       freopen("output.txt","w",stdout);
    #endif
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)
    {
        solve();
        if(t)cout<<"\n";
    }
    return 0;
}

Measured memory_bytes: 3632
n=int(input())
t,a=map(int,input().split())
h_=list(map(int,input().split()))
h=[]
for i in h_:
  hh_=t-6*i/1000
  h.append(hh_)
#print(h)
  
ans=float('inf')

for i in range(n):
  ans=min(ans,abs(a-h[i]))
  if ans==abs(a-h[i]):
    cnt=i
    continue
    
print(cnt+1)
  

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

const int INF = 1e9;
const int MOD = 1e9 + 7;

using namespace std;

typedef long long ll;

#define REP(i, n) for (int i = 0; i < int(n); i++)
#define REPD(i, n) for (int i = n - 1; i >= 0; i--)
#define FOR(i, a, b) for (int i = a; i < int(b); i++)
#define FORD(i, a, b) for (int i = b - 1; i >= int(a); i--)
#define WRAP(y, x, h, w) (0 <= y && y < h && 0 <= x && x < w)

#define ALL(x) (x).begin(), (x).end()

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

int main()
{
    int a, b;
    cin >> a >> b;
    cout << a * (a - 1) / 2 + b * (b - 1) / 2 << endl;
}

Measured memory_bytes: 3600