akhauriyash/Code-Regression huggingface dataset:
N = int(input())

dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(N+1)]
# print(dp)

# dp[i][j][k][l]
# iは文字列の長さ
# j,k,lは最後から1,2,3文字目の文字に対応(A,G,C,Tを0,1,2,3にあてた)

# 長さ0の文字列は1通り
dp[0][3][3][3] = 1
MOD = 10**9 + 7

for i in range(N):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                if dp[i][j][k][l] == 0: # 条件に当てはまるものがない場合はcontinue(これはなくてもok)
                    continue
                for add in range(4): # (i+1)文字目として新しく追加する文字
                    # ダメな5つの条件を捨てる
                    if add == 2 and j == 1 and k == 0:
                        continue
                    if add == 2 and j == 0 and k == 1:
                        continue
                    if add == 1 and j == 2 and k == 0:
                        continue
                    if add == 2 and j == 1 and l == 0:
                        continue
                    if add == 2 and k == 1 and l == 0:
                        continue
                    # ダメな条件を抜けたらaddをi+1番目に足した文字列の個数として数える
                    # S = ...j,k,l から S = ...j,k,l,add へ
                    dp[i+1][add][j][k] += dp[i][j][k][l]
                    dp[i+1][add][j][k] %= MOD

ans = 0
for j in range(4):
    for k in range(4):
        for l in range(4):
            ans += dp[N][j][k][l]
            ans %= MOD

print(ans)

Measured memory_bytes: 3312
//
// Created by Harshit on 25-08-2020.
//
#include <bits/stdc++.h>
using namespace std;
long long res(vector <int> &,int ,int ,long long ,bool );
const int maxx=3005;
long long dp[maxx][maxx][2];
int main(){
    int n;
    long long x=0,y=0;
    cin>>n;
    vector <int> arr(n);
    for(int i=0;i<maxx;i++){
        for(int j=0;j<maxx;j++){
            dp[i][j][0]=LLONG_MIN;
            dp[i][j][1]=LLONG_MIN;
    }
    }
    for(int &x:arr){
        scanf("%d",&x);
        //cout<<x<<" ";
    }
    //cout<<endl;
    for(int j=0;j<n;j++){
        for(int i=n-1;i>-1;i--){
            for(int q:{0,1}){
                if(i>j){
                    dp[i][j][q]=0;
                    continue;
                }
                if(i==j){
                    if(q==0){
                        dp[i][j][q]=arr[i];
                    }
                    else{
                        dp[i][j][q]=(-1)*arr[i];
                    }
                    continue;
                }
                if(q==0){
                    dp[i][j][q]=max(dp[i+1][j][1-q]+(long long)arr[i],dp[i][j-1][1-q]+(long long)arr[j]);
                }
                else{
                    dp[i][j][q]=min(dp[i+1][j][1-q]-(long long)arr[i],dp[i][j-1][1-q]-(long long)arr[j]);
                }
            }
        }
    }
    cout<<dp[0][n-1][0]<<endl;
}

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

int main(){
  string s; cin >> s;
  int n = s.size();
  int ans = 0;
  for(int i = 0; i < n/2; i++){
    if(s[i] != s[n-i-1]) ans++;
  }
  cout << ans << endl;
}

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

void swap(int *, int *);

int main(void)
{
	int n, s, cnt, f1, f2, nl[4], sl[4];
	char in[5];

	while(scanf("%s",in) && strcmp(in, "0000") != 0)
	{	
		if(strcmp(in, "6174") == 0)
			printf("0\n");
		else
		{
			//数値に変換
			for(f1 = 0; f1 < 4; f1++)
			{
				nl[f1] = in[f1] - '0';
				sl[f1] = nl[f1];
			}

			cnt = 0;		
			while(1)
			{
				n = 0;
				s = 0;
				cnt++;
				//並べ替え
				for(f1 = 0; f1 < 3; f1++)
				{
					for(f2 = f1 + 1; f2 < 4; f2++)
					{
						if(nl[f1] < nl[f2])
							swap(&nl[f1],&nl[f2]);
						if(sl[f1] > sl[f2])
							swap(&sl[f1],&sl[f2]);
					}
				}

				for(f1 = 0; f1 < 4; f1++)
				{
					n *= 10;
					n += nl[f1];
					s *= 10;
					s += sl[f1];
				}

				n -= s;
				if(n == 0)
				{
					printf("NA\n");
					break;
				}
				else if(n == 6174)
				{
					printf("%d\n",cnt);
					break;
				}
				else
				{
					for(f1 = 0; f1 < 4; f1++)
					{
						nl[f1] = sl[f1] = n % 10;
						n /= 10;
					}
				}

			}
			
		}
	}
	return 0;
}
void swap(int *p1, int *p2)
{
	int temp;

	temp = *p1;
	*p1 = *p2;
	*p2 = temp;
}

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

ll solve() {
    ll N, A, B;
    cin >> N >> A >> B;
    auto err = []() {
        cout << -1 << "\n";
        return 0;
    };
    if ( A + B - 1 > N ) return err();
    if ( A * B < N ) return err();
    vector<vector<ll>> ans(B, vector<ll>());
    ll x = 1;
    int i;
    for ( i = 0; i < B; i++ ) {
        ans[i].push_back(x);
        x++;
    }
    i = 0;
    while ( x <= N ) {
        while ( ans[i].size() >= A ) i++;
        ans[i].push_back(x);
        x++;
    }

    bool first = true;
    for ( int i = B-1; i >= 0 ; i-- ) {
        for ( auto y : ans[i] ) {
            if ( !first ) cout << " ";
            else first = false;
            cout << y;
        }
    }
    return 0;
}

int main() {
    solve();
    return 0;
}

Measured memory_bytes: 13568
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fi first
#define se second
#define ref(i,x,y)for(int i=x;i<=y;++i)
#define def(i,x,y)for(int i=x;i>=y;--i)
#define eef(i,x)for(int i=head[x],y=e[i].to;y;i=e[i].next,y=e[i].to)
int read(){char c=getchar();int d=0,f=1;for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1;for(;c>='0'&&c<='9';d=d*10+c-48,c=getchar());return d*f;}
char Read(){char c=getchar();while(c<'0'||c>'9')c=getchar();return c;}
int getdigit(char c){return (c<'0'||c>'9')?-1e9:(c-'0');}
typedef pair<int,int>PII;
typedef long long LL;
const double pi=acos(-1);
const int N=1510,mod=1e9+7;
int n,c1[N][N],c2[N][N];LL ans,dp[N][N];
char a[N][N];
int main(){
	n=read();
	ref(i,1,n)scanf("%s",a[i]+1);
	ref(i,1,n){
		if(i==1){
			ref(j,1,n)dp[i][j]=max(0LL,dp[i][j-1]+getdigit(a[i][j]));
			ref(j,1,n)c1[j][1]=j;
			continue;
		}
		ref(j,1,n){
			bool w1=getdigit(a[i][j-1])>=0,w2=getdigit(a[i-1][j])>=0;
			bool W1=getdigit(a[i-1][j-1])>=0,W2=getdigit(a[i-2][j])>=0;
			ref(k,1,i){
				int C1=0;
				if(k==i)C1=j;else{
					if(w1)C1=c1[j-1][k];
					if(w2)C1=max(C1,c1[j][k]);
				}
				c1[j][k]=C1;
			}
			ref(k,1,i-1){
				int C2=1e9;
				if(k==i-1)C2=j;
				if(W1)C2=c2[j-1][k];
				if(W2&&k!=i-1)C2=min(C2,c2[j][k]);
				c2[j][k]=C2;
			}
		}
		ref(j,1,n)if(getdigit(a[i][j])>=0){
			int v=getdigit(a[i][j]);
			bool w1=getdigit(a[i][j-1])>=0,w2=getdigit(a[i-1][j])>=0;
			if(j==1){
				dp[i][j]=dp[i-1][j];
			}else if(j>1){
				if(!w1&&!w2)dp[i][j]=0;else
				if( w1&&!w2)dp[i][j]=dp[i][j-1];else
				if(!w1&& w2)dp[i][j]=dp[i-1][j];else
				if( w1&& w2){
					LL s=dp[i-1][j]+dp[i][j-1],la=1e9;
					def(k,i-1,1){
						if(c1[j-1][k]>=c2[j][k]&&la>c1[j-1][k])
							s-=dp[k][c1[j-1][k]];
						la=c2[j][k];
					}
					dp[i][j]=s;
				}
			}
			dp[i][j]+=v;
		}
	}
	ref(i,1,n)ref(j,1,n){
		int v=getdigit(a[i][j]);
		if(v>=0)ans+=(dp[i][j]-v)*v;
	}
	printf("%lld\n",ans);
}

Measured memory_bytes: 17408
#include<iostream>
#include<cstdio>
#include<string.h>
#include<algorithm>
#include<cmath>
using namespace std;
int a,b,c,d;

int main()
{
    cin>>a>>b>>c>>d;
    if (abs(c-a)<=d || abs(a-b)<=d && abs(b-c)<=d)
    {
        cout<<"Yes"<<endl;
    }else cout<<"No"<<endl;
    return 0;
}


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

int main(){
    string S;
    cin >> S;
    bool difficulty = true;
    for(int i = 0; i < S.size(); i++){
        if(i%2 == 0){
            if(S[i] == 'L')difficulty = false;   //if even is L, then yes
        }
        else{
            if(S[i] == 'R')difficulty = false;   //if odd is R, then yes
        }
    }
    cout << ((difficulty) ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(){
int n,a[31];
a[0]=0;
a[1]=1;
a[2]=2;
for(int i=3;i<=30;i++){
if(i%2==1)a[i]=a[i-1]*2+1;
else a[i]=(a[i-1]-a[i-1]/4)*2;
}
while(scanf("%d",&n)!=EOF){
printf("%d\n",a[n]);
}
}

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

int main() {
    int p,q,ans,r,a,b,c;
    cin >> p >> q >> r;
    a=p+q;
    b=q+r;
    c=r+p;
    ans=min(a,b);
    ans=min(ans,c);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
ll dp[2][3001][3001];
int A[3001];
int main()
{
//  freopen("in.txt", "r", stdin);
//  freopen("out.txt", "w", stdout);
  int n;
  cin >> n;
  for(int i = 0;i < n;i++)
    cin >> A[i];

    for(int j = 1;j <= n;j++){
      for(int k = 0;k + j - 1 < n;k++){
        for(int i = 0;i < 2;i++){
        int s = k, e = k + j - 1;
        if(j == 1){
          dp[i][s][e] = (i == 0 ? A[s] : -A[s]);
        }else{
          if(i == 0)
            dp[0][s][e] = max(dp[1][s + 1][e] + A[s], dp[1][s][e - 1] + A[e]);
          else
            dp[1][s][e] = min(dp[0][s + 1][e] - A[s], dp[0][s][e - 1] - A[e]);
        }
      }
    }
  }
  cout << dp[0][0][n - 1];
  return 0;
}


Measured memory_bytes: 139776
from itertools import permutations

N = int(input())
lx, ly = [], []
for _ in range(N):
    xi, yi = list(map(int, input().split()))
    lx.append(xi)
    ly.append(yi)

fN = 1
for i in range(1, N + 1):
    fN *= i

mcost = 0
for x in permutations(list(range(N))):
    cost = 0.0
    for i in range(len(x) - 1):
        dij = ((lx[x[i]] - lx[x[i + 1]]) ** 2 + (ly[x[i]] - ly[x[i + 1]]) ** 2) ** 0.5
        cost += dij
    mcost += cost / fN
print(mcost)

Measured memory_bytes: 40684
#include<iostream>
using namespace std;
int coin[6]={500,100,50,10,5,1};
int main(){
    int n;
    while(cin>>n,n){
        n=1000-n;
        int cnt=0,i=0;
        while(1){
            if(n-coin[i]>=0){
                n-=coin[i];
                cnt++;
            }
            else i++;
            if(i>=6)break;
        }
        cout<<cnt<<endl;
    }
    return 0;
}

Measured memory_bytes: 1156
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<deque>
#include<queue>
using namespace std;
#define int long  long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
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; }
typedef pair<int, int>P;
const int MOD = 1e9 + 7;
const int INF = 1e10;
const long double PI = (acos(-1));


signed main() {
	int N, K;
	cin >> N >> K;
	if (K == 1)cout << 0 << endl;
	else cout << N - K << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
using namespace std;
int main(){
    char ch;
    int count[100]={};
    while(cin>>ch){
        ch=tolower(ch);
        if(isalpha(ch)){
            int num=ch-'a';
            count[num]++;
        }
    }
    for(int i=0;i<26;i++){
        printf("%c : %d\n", i+'a',count[i]);
    }
}


Measured memory_bytes: 3220
#include<bits/stdc++.h>
#define int long long
#define rep(i,x,y) for(int i=x;i<y;i++)
#define repr(i,x,y) for(int i=x;i>=y;i--) 
#define mod 1000000007
using namespace std;

void Onigiri()
{
  int k;
  cin>>k;
  string s;
  cin>>s;
  for(int i=0;i<s.length();i++)
  {
    if(i>=k)
      {cout<<"...";break;}
    else cout<<s[i];
  }
}
signed main()
{
   ios_base::sync_with_stdio(false);cin.tie(NULL);
   #ifdef Zoro
   freopen("in", "r", stdin);freopen("out", "w", stdout);
   #endif  
 
   int t=1; 
   //cin>>t;
 
   while(t--)
   {Onigiri();cout<<"\n";}

   cerr<<"\n"<<(float)clock()/CLOCKS_PER_SEC*1000<<" ms"<<endl;
   return 0;
}   

Measured memory_bytes: 3792
#include<stdio.h>
#define MAX 10000

main(){
  int i,j,n,q,count = 0;
  int S[MAX],T[MAX];
  
  scanf("%d",&n);
  for(i = 0;i < n;i++){
    scanf("%d",&S[i]);
  }
  scanf("%d",&q);
  for(i = 0; i < q;i++){
    scanf("%d",&T[i]);
  }
  
  for(i = 0; i < q; i++){
    for(j =0; j < n; j++)
      if(T[i] == S[j]){
        count++;
        break;
      }
  }
  printf("%d\n",count);
 
return 0;
}

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

public class Main {

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

	    int N=gi();
	    int[] D=new int[N];
	    for (int i=0; i<N; i++) {
	    	D[i]=gi();
	    }
	    
	    int M=gi();
	  int[] T=new int[M];  
      for (int i=0; i<M; i++) {
	    	T[i]=gi();
	    }
	    
	    Arrays.parallelSort(D);
	    Arrays.parallelSort(T);
	    
	    int index=0;
	    for (int i=0; i<M;i++) {
	    	int t=T[i];
	    	while(t!=D[index]) {
	    		if (D[index]>t || index==N-1) {
	    			System.out.print("NO");
	    			return;
	    		}
	    		index++;
	    	}
	    	index++;
	    }
        System.out.println("YES");
//	    if(max>s-max) {
//	    	System.out.println(s-max-1);
//	    }
	}

	// 文字列として入力を取得
	public static String gs() {
		return scanner.next();
	}

	// intとして入力を取得
	public static int gi() {
		return Integer.parseInt(scanner.next());
	}

	// longとして入力を取得
	public static long gl() {
		return Long.parseLong(scanner.next());
	}

	// doubleとして入力を取得
	public static double gd() {
		return Double.parseDouble(scanner.next());
	}
}

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


int main()
{
	int k, d, c;
	cin >> k >> d >> c;
	if(d%k == 0)
		cout << "OK\n";
	else if( c >= k*(d/k + 1))
		cout << " OK\n";
	else
		cout << "NG\n";
	return 0;
}

Measured memory_bytes: 3608
#include<iostream>
#include<vector>
#include<string>

using namespace std;

int main(){
	int ans,n,h;
	string m1,m2;
	int a[4]={1000,100,10,1};
	char c[4]={'m','c','x','i'};
	vector<char>m;
	cin>>n;
	while(n--){
		ans=0;
		h=1;
		int f,g;
		cin>>m1>>m2;
		m.clear();
		f=m1.size();
		for(int i=0;i<f;i++){
			for(int j=0;j<4;j++){
				if(m1[i]==c[j]){
					ans+=a[j]*h;
					h=1;
					break;
				}
			}
			if(m1[i]>='0'&&m1[i]<='9')h=m1[i]-'0';
		}
		g=m2.size();
		h=1;
		for(int i=0;i<g;i++){
			for(int j=0;j<4;j++){
				if(m2[i]==c[j]){
					ans+=a[j]*h;
					h=1;
					break;
				}	
			}
			if(m2[i]>='0'&&m2[i]<='9')h=m2[i]-'0';
		}
		while(ans){
			int i=0;
			for(i=0;i<4;i++){
				if(ans/a[i]>=1){
					if(ans/a[i]==1){
						m.push_back(c[i]);
						break;
					}
					else{
						m.push_back(ans/a[i]+'0');
						m.push_back(c[i]);
						break;
					}
				}
			}
			ans-=ans/a[i]*a[i];
		}
		vector<char> ::iterator it=m.begin();
		while(it != m.end()){
			cout<<*it;
			++it;
		}
		cout<<endl;
	}

	return 0;
}

Measured memory_bytes: 1220
#define _USE_MATH_DEFINES
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>

using namespace std;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 29;
const int MOD = 1e9 + 7;

int main() {
  int n, m;
  cin >> n >> m;
  if (n % m) {
    cout << 1 << endl;
  } else {
    cout << 0 << endl;
  }
  return 0;
}


Measured memory_bytes: 256
A,B=map(int,input().split())
import sys
input=sys.stdin.readline
sys.setrecursionlimit(1000000000)
def gcd(a,b):#最大公約数を返す。Euclid
    if a<b:
        a,b=b,a
    if b==0:
        return a
    return gcd(b,a%b)
c=gcd(A,B)
#print(c)
sqrtc=int(c**(1/2))
vc=c
ans=1
for i in range(2,sqrtc+1):
    if vc%i==0:
        ans+=1
        vc/=i
        while vc%i==0:
            vc/=i
if vc!=1:
    ans+=1
print(ans)


Measured memory_bytes: 3188
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = True

r = INT()
print(2 * r * pi)

Measured memory_bytes: 74144
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
	string a, b;
	cin >> a >> b;
	
	sort(a.begin(), a.end());
	sort(b.rbegin(), b.rend());

	if (a < b) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 200000 + 15;
int canti[maxn], pro[maxn];
int main()
{
	//freopen("Text.txt", "r", stdin);
	int m,n;
	while (scanf("%d",&n)==1)
	{
		for (int i = 0; i < n; i++)
		{
			scanf("%d", &canti[i]);
		}
		scanf("%d", &m);
		for (int i = 0; i < m; i++)
		{
			scanf("%d", &pro[i]);
		}
		if (n < m)
		{
			printf("NO\n");
			continue;
		}
		sort(canti, canti + n);
		sort(pro, pro + m);
		int j=0,i=0;
			while(i<m&&j<n)
			{
				if (pro[i] > canti[j])
				{
					j++;
				}
				else if(pro[i]==canti[j])
				{
					i++;
					j++;
				}
				else
				{
					printf("NO\n");
					break;
				}
			}
			if (i == m) printf("YES\n");
	}
	return 0;
}

Measured memory_bytes: 1664
#include <cstring>
#include <sstream>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <set>
#include <numeric>
#include <stack>

using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = n - 1; i >= 0; i--)
#define repone(i, n) for(ll i = 1; i <= (ll)(n); i++)
#define each(i, mp) for(auto i:mp)
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll half_inf = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);
typedef unordered_map<ll, ll> ump;
typedef pair<ll, ll> P;

ump mp;

int main() {
#ifdef MY_DEBUG
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wmissing-noreturn"
    while (true) {
        mp = ump();
#pragma clang diagnostic pop
#endif
        ll n, W;
        cin >> n >> W;
        ll w[n], v[n];
        rep(i, n) cin >> w[i] >> v[i];

        ll dp[n + 1][half_inf + 100];
        rep(i, n + 1) rep(j, half_inf + 100) dp[i][j] = ll_inf;
        dp[0][0] = 0;

        rep(i, n) {
            rep(j, half_inf + 100) {
                dp[i + 1][j] = dp[i][j];
                if (j >= v[i] && dp[i][j - v[i]] != ll_inf) {
                    dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - v[i]] + w[i]);
                }
            }
        }

        ll ans = 0;
        rep(i, half_inf + 100) {
            if (dp[n][i] <= W) ans = max(i, ans);
        }
        cout << ans << endl;

#ifdef MY_DEBUG
    }
#endif
    return 0;
}

Measured memory_bytes: 79232
s=input()
i=0
flag=0
while i<len(s):
    if (i+1)%2==0:
        if s[i] =="L" or s[i] =="U" or s[i] =="D":
            pass
        else:
            flag+=1
         
    else:
        if s[i] =="R" or s[i] =="U" or s[i] =="D":
            pass
        else:
            flag+=1
     

    if flag==1:
        break


    i+=1

if flag==1:
    print("No")
else:
    print("Yes")

Measured memory_bytes: 9136
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <cstring>
#include <utility>
#include <numeric>

using namespace std;

int main(){

    int H, W, M;
    cin >> H >> W >> M;
    vector<pair<int, int>> hw(M);
    vector<int> cntH(H, 0);
    vector<int> cntW(W, 0);

    int h, w;
    for(int i = 0; i < M; i++){
        cin >> h >> w;
        cntH[h - 1]++;
        cntW[w - 1]++;
        hw[i] = make_pair(h - 1, w - 1);
    }

    int maxCntH = *max_element(cntH.begin(), cntH.end());
    int maxCntW = *max_element(cntW.begin(), cntW.end());

    vector<int> maxIndexH, maxIndexW;
    for(int i = 0; i < H; i++){
        if(cntH[i] == maxCntH){
            maxIndexH.push_back(i);
        }
    }

    for(int i = 0; i < W; i++){
        if(cntW[i] == maxCntW){
            maxIndexW.push_back(i);
        }
    }

    long long s = (int)maxIndexH.size() * (int)maxIndexW.size();
    if(s > M){
        cout << maxCntH + maxCntW << endl;
    }
    else{
        int cnt = 0;
        for(auto temp: hw){
            int x = temp.first;
            int y = temp.second;
            if(binary_search(maxIndexH.begin(), maxIndexH.end(), x)){
                if(binary_search(maxIndexW.begin(), maxIndexW.end(), y)){
                    cnt++;
                }
            }
        }

        if(cnt == s){
            cout << maxCntH + maxCntW - 1 << endl;
        }
        else{
            cout << maxCntH + maxCntW << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 12084
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    vector<int> A(3, 0); cin >> A[0] >> A[1] >> A[2];
    sort(A.begin(), A.end());
    if (A[0] != A[1]) printf("%d\n", A[0]);
    else if (A[2] != A[1]) printf("%d\n", A[2]);
}

Measured memory_bytes: 3736
import java.util.*;

public class Main {

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

        int n = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int d = sc.nextInt();
        String s = sc.next();
        
        s = s.substring(a-1, Math.max(c,d));

        if (s.contains("##")){
            System.out.println("No");
        }else if ((b<c && c<d) || (c<b && b<d)){
            System.out.println("Yes");
        }else if (b<d && d<c){
            if (s.substring(b-2, d+1).contains("...")){
                System.out.println("Yes");
            }else{
                System.out.println("No");
            }
        }


    }

}



Measured memory_bytes: 27544
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>


using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e16;
const ll MOD = 1e9 + 7;

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




int main() {
    string s, ans;
    ll w;
    cin >> s >> w;
    for(ll i = 0; i < s.size(); i += w){
        ans += s[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace __gnu_pbds;
using namespace std;
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define PSET(x,y) fixed<<setprecision(y)<<x
#define pb push_back
#define pf push_front
#define mp make_pair
#define pii pair<int,int>
#define pid pair<int,double>
#define vi vector<int>
#define ff first
#define ss second
#define int long long int
#define ull unsigned long long
#define PI 3.14159265
#define SIZE 200010
#define MOD 1000000007
#define BIG 998244353
#define s(t) scanf("%d",&t)
#define p(t) printf("%d\n",t)
#define mii map<int,int>
#define tc int tcs;cin>>tcs;while(tcs--)
#define set_bit __builtin_popcount
#define MSET(table,i) memset(table, i, sizeof(table))
int toint(const string &s) {stringstream ss; ss << s; int x; ss >> x; return x;}
string tostring ( int number ){stringstream ss; ss<< number; return ss.str();}
 
int32_t main()
{
  string s;
  cin>>s;
    char prev='.';
    int n=s.length();
  for(int i=0;i<n;i++)
  {
      if(s[i]=='?')
      {
          if(prev=='P')
          {
              s[i]='D';
          }
          else
          {
              if(i+1 < n && s[i+1]=='D')
              {
                  s[i]='P';
              }
              else
              s[i]='D';  
          }
      }
      prev=s[i];
  }
  cout<<s;
}

Measured memory_bytes: 3732
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<utility>
#include<iostream>
using namespace  std;
 
const int maxn = 105;
int n,p,a = 0,b = 0;
 
long long slove(int x,int y){
	long long sum = 1;
	int tot = max(x - y,y);
	for(int i = x;i >= tot + 1;i--) sum = (sum * i) / (x - i + 1);
	return sum;
}
 
int main(){
	long long sum_a = 0,sum_b = 0,sum = 0;
	scanf("%d %d",&n,&p);
	for(int i = 1;i <= n;i++){
		int x;
		scanf("%d",&x);
		if(x % 2 != 0) a++;
		else b++;
	}
	for(int i = 1;i <= b;i++){
			if(i == b) sum_b++;
			else sum_b += slove(b,i);
	}
	if(p == 0){
		int ans = 2;
		while(ans <= a){
			if(ans == a) sum_a++;
			else{
				sum_a += slove(a,ans);
			}
			ans += 2;
		}
		sum = sum_b + sum_a + sum_b * sum_a + 1;
	}
	else{
		int ans = 1;
		while(ans <= a){
			if(ans == a) sum_a++;
			else{
				sum_a += slove(a,ans);
			}
			ans += 2;
		}
		sum = sum_a + sum_a * sum_b;
	}
	printf("%lld",sum);
}

Measured memory_bytes: 256
from itertools import product

H, W, K = map(int, input().split())
l = [input() for _ in range(H)]

ans = 0
for s in product(range(2), repeat=H):
    for t in product(range(2), repeat=W):
        res = [[0]*W for _ in range(H)]

        for i, ri in enumerate(s):
            for j, rj in enumerate(t):
                if ri or rj:
                    res[i][j] = 1
        cnt = 0
        for i in range(H):
            for j in range(W):
                if res[i][j]==0 and l[i][j]=="#":
                    cnt += 1
        ans += (cnt==K)
print(ans)


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

using namespace std;
#define LL long long

const int MAXN = 212345;

LL lcm (LL a, LL b) {
	return a / __gcd (a, b) * b;
}

int main () {

	ios_base::sync_with_stdio(false); cin.tie(NULL);

	LL a, b, c, d;
	cin >> a >> b >> c >> d;

	LL x = b / c - (a - 1) / c;
	LL y = b / d - (a - 1) / d;

	// cout << "x= " << x << ' ' << "y= " << y << '\n';

	LL k = lcm (c, d);

	LL both = b / k - (a - 1) / k;
	LL used = x + y - both;

	LL inter = b - a + 1;
	LL resp = inter - used;

	cout << resp << '\n';

	/*
	for (int i = a; i <= b; ++i) {
		cout << i;
		if (i % c==0 || i % d==0) cout << "* ";
		cout << ' ';
	}

	cout << endl;
	*/

	return 0;
}


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

a.sort()
count = 0
for i in range(n-1):
    x -= a[i]
    if x >= 0:
        count += 1
    else:
        break
if x == a[n-1]:
    count += 1

print(count)


Measured memory_bytes: 3060
import java.util.*;
import java.util.Map.Entry;
import java.io.*;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.rmi.server.UnicastRemoteObject;

import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
 
public class Main //implements Runnable
{
    static long mod=1000000007;
//    static int dx[]={-1,0,1,0};
//    static int dy[]={0,-1,0,1};

    public static void main(String[] args)   throws Exception, IOException{        
        Reader sc = new Reader(System.in);
        PrintWriter out=new PrintWriter(System.out);

        int m=sc.nextInt();
        int d=sc.nextInt();
        int a=0;
        for (int i = 1; i <= m; i++) {
			for (int j = 21; j <= d ; j++) {
				if(j%10<2)continue;
				if(i == (j%10)*(j/10)) {
//					db(i,j);
					a++;
				}
			}
		}
        
        out.println(a);
     	out.flush();
    }
    
    static boolean validpos(int x,int y,int r, int c){
        return x<r && 0<=x && y<c && 0<=y;
    }

    static void db(Object... os){
        System.err.println(Arrays.deepToString(os));
    }
}

//class P {
//	int x, y;
//	P(int  x, int y) {
//	  this.x=x;
//	  this.y=y;
//	}
//}

//class P implements Comparable<P>{
//    int a,b;
//    P(int a, int b) {
//    	this.b=b;
//    	this.a=a;
//    }
//
//    public int compareTo(P p){
//    	if(a==p.a) return b-p.b;
//        return -p.a+a;
//    }
//}

class Reader
{ 
    private BufferedReader x;
    private StringTokenizer st;
    
    public Reader(InputStream in)
    {
        x = new BufferedReader(new InputStreamReader(in));
        st = null;
    }
    public String nextString() throws IOException
    {
        while( st==null || !st.hasMoreTokens() )
            st = new StringTokenizer(x.readLine());
        return st.nextToken();
    }
    public int nextInt() throws IOException
    {
        return Integer.parseInt(nextString());
    }
    public int[] nextIntArray(int size) throws IOException{
        int r[] = new int[size];
        for (int i = 0; i < size; i++) {
            r[i] = this.nextInt(); 
        }
        return r;
    }
    public long[] nextLongArray(int size) throws IOException{
        long r[] = new long[size];
        for (int i = 0; i < size; i++) {
            r[i] = this.nextLong(); 
        }
        return r;
    }
    public long nextLong() throws IOException
    {
        return Long.parseLong(nextString());
    }
    public double nextDouble() throws IOException
    {
        return Double.parseDouble(nextString());
    }
}


Measured memory_bytes: 21076
#include <bits/stdc++.h>
using namespace std;
#define fst ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endk cout<<"\n";
typedef long long int ll;
typedef long int l;
#define l(i,a,b) for(i=a;i<b;i++)
#define lo(i,a,b) for(i=a;i>=b;i--)
#define s(v) sort(v.begin(),v.end());
#define pb push_back;
#define vll vector<ll>
#define vint vector<int>
#define test() ll t;cin>>t;while(t--){solve();};
#define test1() int t=1;while(t--){solve();};
bool isPrime(ll x)
{
    ll i,n;
    n=sqrt(x);
    if(x==1) return false;
    if(x==2 || x==3) return true;
    for(i=2;i<=n;i++)
    {
        if(!(x%i)) return false;
    }
    return true;
}
ll power(ll x,ll y)
{
	ll ans=1;
	while(y>0)
	{
		if(y&1) ans=ans*x;
		x=x*x;
		y=y>>1;
	}
	return ans;
}
int solve()
{
    ll n,i,ans=0,j;
    cin>>n;
    vll v(n),x(n,0);
    for(i=0;i<n;i++)
    {
        cin>>v[i];
    }
    for(i=n-2;i>=0;i--)
    {
        x[i]=(x[i+1]+v[i+1])%1000000007;
    }
    for(i=0;i<n;i++)
    {
        ans=(ans+(v[i]*x[i])%1000000007)%1000000007;
    }
    cout<<ans;
    return 0;
}
int main()
{
    fst;
    test1();
    return 0;
}

Measured memory_bytes: 6364
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<stack>
#define inf 0x3f3f3f3f
#define esp 1e-7
using namespace std;
int read(){
    int x=0,f=1;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 t,n,m;
int num[310][310];
int sp[310];

int main(){
	n=read();m=read();
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			num[i][j]=read();
		}
	}
	int maxx=0,minn=1<<30;
	memset(sp,0,sizeof(sp));
	for (int i=1;i<=n;i++)	num[i][0]=1;
	for (int i=1;i<=m;i++){
		maxx=0;
		for (int j=1;j<=m;j++){
			if (sp[j]!=-1){
				sp[j]=0;
			}
		}
		//for (int j=1;j<=n;j++)	cout<<num[j][0];
		//printf("\n");
		for (int j=1;j<=n;j++){
			while (sp[num[j][num[j][0]]]==-1&&num[j][0]<=m){
				num[j][0]++;
			}
			if (num[j][0]<=m) sp[num[j][num[j][0]]]++;
		}
		for (int j=1;j<=m;j++){
			maxx=max(maxx,sp[j]);
		}
		if (maxx==-1)	break;
		minn=min(minn,maxx);
		for (int j=1;j<=m;j++){
			if (sp[j]==maxx){
				//cout<<"spj="<<sp[j]<<' '<<j<<endl;
				sp[j]=-1;
				for (int k=1;k<=n;k++){
					if (num[k][num[k][0]]==j)
						num[k][0]++;
				}
				break;
			}
		}
		//cout<<minn<<' '<<maxx<<endl;
		maxx=0;
	}
	cout<<minn<<endl;
	return 0;
}

Measured memory_bytes: 640
import java.io.*;
import java.util.*;
class Main{
	static final long MOD = 1_000_000_007; // 10^9+7
    static final int MAX = 2_147_483_646; // intMax 
    static final int INF = 1_000_000_000; // 10^9  
    public static void main(String[] args) throws Exception {
		hayami saori = new hayami();
		int A = saori.saori_hayami();
		int B = saori.saori_hayami();
		if(A <=8 && B <= 8) {
			System.out.println("Yay!");
		}
		else {
			System.out.println(":(");
		}
		saori.close();
    }
}

class hayami implements Closeable {
	private final InputStream in = System.in;
	private final byte[] hayami = new byte[1024];
	private int Hayami = 0;
	private int saori = 0;
	private boolean HayamiSaori() {
		if (Hayami < saori) {
			return true;
		}else{
			Hayami = 0;
			try {
				saori = in.read(hayami);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (saori <= 0) {
				return false;
			}
		}
		return true;
	}
	private int SaoriHayami() { 
		if (HayamiSaori()) {
            return hayami[Hayami++];
         }else{
             return -1;
         }
	}
	private static boolean hayami_saori(int hayami) { 
		return 33 <= hayami && hayami <= 126;
	}
	public boolean hayamisaori() { 
		while(HayamiSaori() && !hayami_saori(hayami[Hayami])) Hayami++; return HayamiSaori();
	}
	public String nextHayami() {
		if (!hayamisaori()) throw new NoSuchElementException();
		StringBuilder hayamin = new StringBuilder();
		int saori = SaoriHayami();
		while(hayami_saori(saori)) {
			hayamin.appendCodePoint(saori);
			saori = SaoriHayami();
		}
		return hayamin.toString();
	}
	public long saorihayami() {//nextLong
		if (!hayamisaori()) throw new NoSuchElementException();
		long hayami = 0;
		boolean misao = false;
		int saori = SaoriHayami();
		if (saori == '-') {
			misao = true;
			saori = SaoriHayami();
		}
		if (saori < '0' || '9' < saori) {
			throw new NumberFormatException();
		}
		while(true){
			if ('0' <= saori && saori <= '9') {
				hayami *= 10;
				hayami += saori - '0';
			}else if(saori == -1 || !hayami_saori(saori)){
				return misao ? -hayami : hayami;
			}else{
				throw new NumberFormatException();
			}
			saori = SaoriHayami();
		}
	}
	public int saori_hayami() {//nextInt
		long hayami = saorihayami();
		if (hayami < Integer.MIN_VALUE || hayami > Integer.MAX_VALUE) throw new NumberFormatException();
		return (int) hayami;
	}
	public double Hayamin() { //nextDouble
		return Double.parseDouble(nextHayami());
	}
	public void close() {
		try {
			in.close();
		} catch (IOException e) {
		}
    }
    
}

Measured memory_bytes: 23252
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define _ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define cases(x, ...) int T; cin >> T; \
                      for (int current_test_case = 1; current_test_case <= T; current_test_case++) { \
                          if (x) cout << "Case " << current_test_case << ": "; \
                          __VA_ARGS__ \
                      }

const int inf = 1e18;
const int mod = 1e9 + 7;
const int maxn = 6e6 + 6;
const double eps = 1e-9;

int32_t main(void) { _
    int arr[4][4], a[4], b[4];
    cin >> arr[1][1] >> arr[1][2] >> arr[1][3];
    cin >> arr[2][1] >> arr[2][2] >> arr[2][3];
    cin >> arr[3][1] >> arr[3][2] >> arr[3][3];
    a[1] = 0;
    b[1] = arr[1][1];
    b[2] = arr[1][2];
    b[3] = arr[1][3];
    a[2] = arr[2][1] - b[1];
    a[3] = arr[3][1] - b[1];
    for (int i = 1; i <= 3; i++) {
        for (int j = 1; j <= 3; j++) {
            if (a[i] + b[j] != arr[i][j]) return cout << "No", 0;
        }
    }
    cout << "Yes";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using vi=vector<int>;
using vvi=vector<vi>;
using vs=vector<string>;
using msi=map<string,int>;
using mii=map<int,int>;
//using pii=pair<int,int>;
using vlai=valarray<int>;
using ll=long long;
using pii=pair<ll,ll>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define INF 1e9
#define EPS 1e-9
#define MOD (1e9+7)
void get(){}template<class H,class...T>void get(H&h,T&...t){cin>>h;get(t...);}
#define dcl(...) ll __VA_ARGS__;get(__VA_ARGS__);


int main(){
    dcl(n,a,b);
    cout<<(n-a)%b<<endl;
}


Measured memory_bytes: 256
# original: https://atcoder.jp/contests/abc152/submissions/9634969
# test the difference between implementation of popcount
N = int(input())
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)

P = [-1] * N
DE = [0] * N
Q = [0]
while Q:
    i = Q.pop()
    for a in X[i][::-1]:
        if a != P[i]:
            P[a] = i
            DE[a] = DE[i] + 1
            X[a].remove(i)
            Q.append(a)

def lp(u, v):
    t = 0
    while u != v:
        if DE[u] > DE[v]:
            t += 1 << u-1
            u = P[u]
        elif DE[u] < DE[v]:
            t += 1 << v-1
            v = P[v]
        else:
            t += 1 << u-1
            t += 1 << v-1
            u = P[u]
            v = P[v]
    
    return t

Y = []
M = int(input())
for _ in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    Y.append(lp(a, b))

def popcnt(n):
    return bin(n).count("1")

D = {1<<i: i for i in range(50)}
Z = [0] * (1<<M)
ans = 0
CC = [0] * N
for m in range(1<<M):
    a = m & (-m)
    if a == m:
        if a == 0:
            Z[m] = 0
        else:
            Z[m] = Y[D[a]]
    else:
        Z[m] = Z[m^a] | Y[D[a]]
    
    CC[N - 1 - popcnt(Z[m])] += (1 if popcnt(m) & 1 == 0 else -1)

print(sum([2 ** i * CC[i] for i in range(N)]))


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


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

  vector<uint64_t> A(N,0), B(N,0);

  for(uint64_t i=0;i<N;i++){
    cin >> A[i];
  }
  

  for(uint64_t i=0; i <= N-2; i++){
    int j = N-2 - i;
    B[j] = (B[j+1] + A[j+1]) % 1000000007; 
  }

  uint64_t sum=0;
  
  for(uint64_t i=0;i<=N-2;i++){
    sum = (sum + (( A[i] * B[i]) % 1000000007) )% 1000000007;
  }

  cout << sum << endl;

}


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

int main(){
  int a,b,i;
  string s;
  cin>>a>>b;
  cin>>s;
  if(s[a]!='-'){
    cout<<"No";
    return 0;
  }
  for(i=0;i<a;i++){
    if('0'>s[i] || s[i]>'9'){
      cout<<"No";
      return 0;
    }
  }
  for(i=a+1;i<a+b+1;i++){
    if('0'>s[i] || s[i]>'9'){
      cout<<"No";
      return 0;
    }
  }
  cout<<"Yes";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
int main(){
    ios::sync_with_stdio(false);
    string str;
    cin >> str;
    reverse(str.begin(), str.end());
    int n = str.size();
    vector<int> a(n), s(n+1);
    int pow_10_mod = 1;
    s[0] = 0;
    rep(i, n) {
        a[i] = ((str[i]-'0')*pow_10_mod)%2019;
        s[i+1] = (s[i] + a[i])%2019;
        pow_10_mod = (pow_10_mod*10)%2019;
    }
    vector<int> cnt(2019);
    int ans = 0;
    rep(i,n+1) {
        ans += cnt[s[i]];
        cnt[s[i]]++;
    }
    cout << ans << endl;
}

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

const int nm = 1e5;
int n, m, h[nm], c = 0;
bool g[nm];

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> h[i];
	fill(g, g + n, 1);
	for (int i = 0, a, b; i < m; i++) {
		cin >> a >> b;
		a--, b--;
		if (h[a] <= h[b])
			g[a] = 0;
		if (h[b] <= h[a])
			g[b] = 0;
	}
	for (int i = 0; i < n; i++)
		if (g[i])
			c++;
	cout << c << endl;
}


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

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    sort(A.begin(), A.end());
    cout << abs(A[0] - A[N - 1]) << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <functional>
#include <algorithm>
#include <vector>
#include <limits>
#include <numeric>
#include <type_traits>
#include <iostream>
#include <queue>
#include <bits/stdc++.h>

#define INF (1ll<<60)
#define MOD 1000000007
#define BOUND 27182818284

typedef long long ll;
typedef long long int lli;

#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)

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

using namespace std;

// gcd
int gcd(int a, int b){
    if(a==0)
        return b;
    return gcd(b%a,a);
}
// gcd array
int findGCD(int arr[], int n){
    int result = arr[0];
    for (int i=1; i < n; i++)
        result = gcd(arr[i], result);

    return result;
}

// sort big to small
// sort(A,A+N, greater<int>());

// v.front() = -BOUND;
// v.back() = BOUND;

// Iterator
// v.begin
// v.end

int main() {
    int a,b,c,d;
    string N;
    cin >> N;

    a = N[0] - '0';
    b = N[1] - '0';
    c = N[2] - '0';
    d = N[3] - '0';

    if (a -b -c - d ==7)
        printf ("%d-%d-%d-%d=7\n " ,a ,b ,c , d );
    else if (a -b - c + d ==7)
        printf ("%d-%d-%d+%d=7\n " ,a ,b ,c , d );
    else if (a - b +c - d ==7)
        printf ("%d-%d+%d-%d=7\n " ,a ,b ,c , d );
    else if (a - b + c + d ==7)
        printf ("%d-%d+%d+%d=7\n " ,a ,b ,c , d );
    else if ( a +b -c - d ==7)
        printf ("%d+%d-%d-%d=7\n " ,a ,b ,c , d );
    else if ( a +b - c + d ==7)
        printf ("%d+%d-%d+%d=7\n " ,a ,b ,c , d );
    else if ( a + b +c - d ==7)
        printf ("%d+%d+%d-%d=7\n " ,a ,b ,c , d );
    else if ( a + b + c + d ==7)
        printf ("%d+%d+%d+%d=7\n " ,a ,b ,c , d );

    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin>>s;
  int a=0,b=0,ans=0;
    for(int i=0;i<(int)s.length();++i)
    {
        if(s[i]=='0')
        a++;
        else
        {
            b++;
        }
        
    }
    cout << 2*min(a,b);

}

Measured memory_bytes: 512
#include <stdio.h>

int main()
{
  int A[1000],N,i,j,v;

  scanf("%d",&N);
  for(j=0;j<N;j++){
    scanf("%d",&A[j]);
  }
  
  for(j=0;j<N-1;j++){
    printf("%d ",A[j]);
    }
  printf("%d\n",A[N-1]);

  for(i=1;i<=N-1;i++){
    v=A[i];
    j=i-1;
    while(j>=0 && A[j]>v){
      A[j+1]=A[j];
      j--;
      A[j+1]=v;
    }
    for(j=0;j<N-1;j++){
      printf("%d ",A[j]);
    }
    printf("%d\n",A[N-1]);
     
  }
  
  return 0;
}

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

using namespace std;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 1LL<<60;

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

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

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


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

  int x, y;
  cin >> x >> y;

  if(y%2==1){
    cout << "No" << endl;
    return 0;
  }

  if(2*x <= y && y <= 4*x){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }


  return 0;
}


Measured memory_bytes: 3652
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

setrecursionlimit(10000)

N = read()
a = [x-1 for x in reads()]

print(sum(a[a[i]] == i for i in range(N)) // 2)


Measured memory_bytes: 14564
import math
import sys
A,B = map(int,input().split())
x = math.floor(A/0.08)
y = math.floor(B/0.1)
for i in range(min(x,y),max(x,y)+3):
    s = math.floor(i*0.08)
    t = math.floor(i*0.1)
    if s == A and t == B:
        print(i)
        sys.exit()
print(-1)

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> k(n), mm(m, 0);
  vector<vector<int>> a(n);
  rep(i, 0, n) {
    cin >> k[i];
    rep(j, 0, k[i]) {
      int b;
      cin >> b;
      a[i].push_back(b-1);
      mm[b-1]++;
    }
  }
  int c = 0;
  rep(i, 0, m) {
    if(mm[i] == n) {
      c++;
    }
  }
  cout << c;
}


Measured memory_bytes: 3616
#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()
#define _GLIBCXX_DEBUG

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vd = vector<double>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using vvd = vector<vd>;
using vvvi = vector<vvi>;
using vvvll = vector<vvll>;
using vvvd = vector<vvd>;

const double pi=3.141592653589793;
const ll MOD=1e9+7;

int main() {
    int n;
    cin>>n;
    ll a[n];
    ll c=0;//負数の数
    ll s=0;//絶対値の合計
    ll m=100000000000;//絶対値の最小
    int b=0;//0が存在するか
    rep(i,n){
        cin>>a[i];
        s+=abs(a[i]);
        if (a[i]==0){
            b=1;
        }
        if (a[i]<0){
            c+=1;
        }
        m=min(m,abs(a[i]));
    }
    if(b){
        cout<<s<<endl;
    }
    else{
        if (c%2==0){
            cout<<s<<endl;
        }
        else{
            cout<<s-2*m<<endl;
        }
    }

    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define int         int long long
#define pb          push_back
#define pii         pair<int,int>
#define vi	        vector<int>
#define mii        map<int,int>
#define fs           first
#define sc          second
#define  M        1000000007
#define fr for(int i=0;i<n;i++)
#define f(i,a,b) for(int i=a;i<b;i++)
#define fm(i,a,b) for(int i=a;i>b;i--)
    
using namespace std;

signed main()
{	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int test=1;
    //cin>>test;
    while(test--){
        int a,b,c;
        cin>>a>>b>>c;
        if((a==b&&b!=c)||(a==c&&c!=b)||(b==c&&c!=a)) cout<<"Yes\n";
        else cout<<"No";

    }
    return 0;
}       

Measured memory_bytes: 256
x1, y1, x2, y2 = map(int, input().split())

dx = x2 - x1
dy = y2 - y1

x3 = x2 - dy
y3 = y2 + dx

x4 = x1 - dy
y4 = y1 + dx

print(str(x3) + ' ' + str(y3) + ' ' + str(x4) + ' ' + str(y4))

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
vector<int> G[100000];
int group[100000]={0};

void dfs(int v,int g){
	group[v] = g;
	for(int i=0;i<G[v].size();i++)
		if(!group[G[v][i]]) 
			dfs(G[v][i],g);
}

int main()
{	
	int n,m,u,v;
	cin>>n>>m;
	while(m--){
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	int g = 1;
	for(int i=0;i<n;i++)
		if(!group[i]) dfs(i,g++);
	cin>>m;
	while(m--){
		scanf("%d%d",&u,&v);
		if(group[u]==group[v])
			puts("yes");
		else puts("no");
	}
	return 0;
}


Measured memory_bytes: 12080