akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
const bool debug=false;
#define DEBUG if(debug==true)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll n;
// 0:a,1:t,2:g,3:c
int main(void) {
    cin >> n;
    ll dp[n+1][4][4][4]={};
    rep(i,4)rep(j,4)rep(k,4){
        if(i==0&&j==2&&k==3)continue;
        if(i==2&&j==0&&k==3)continue;
        if(i==0&&j==3&&k==2)continue;
        dp[3][i][j][k]=1;
    }
    for(int a=4;a<n+1;a++)rep(i,4)rep(j,4)rep(k,4){
        if(i==0&&j==2&&k==3)continue;
        if(i==2&&j==0&&k==3)continue;
        if(i==0&&j==3&&k==2)continue;
        rep(l,4){
            if(l==0&&i==2&&k==3)continue;
            if(l==0&&j==2&&k==3)continue;
            dp[a][i][j][k]+=dp[a-1][l][i][j];
            dp[a][i][j][k]%=1000000007;
        }
    }
    ll res=0;
    rep(i,4)rep(j,4)rep(k,4){
        res += dp[n][i][j][k];
        res %= 1000000007;
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main (){
  int N;
  cin>>N;
  int l,r,sum;
  l=0;
  r=0;
  sum=0;
  for (int i=0;i<N;i++){
    cin>>l>>r;
    sum +=(r-l+1);
  }
  cout<<sum<<endl;
}


Measured memory_bytes: 3604
#include<bits/stdc++.h>
using namespace std;
bool isprime(long long s)
{
	bool f=true;
	for(long long i=2;i<s/2;i++)
	if(s%i==0) f=false;
	if(s>1) return f;
	else return false;
}
int main()
{
	long long x;
	cin>>x;
	for(long long i=x;;i++)
	if(isprime(i)) 
	{
		cout<<i;
		return 0;
	}
	return 0;
}


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

int main(){
    int n;
    scanf("%d", &n);
    int s1, s2;
    int diff, min;
    int input;

    vector<int> array;
    for (int i=0; i < n; i++) {
        cin >> input;
        array.push_back(input);
    }

    for (int i=0; i < n; i++) {
      s1 = accumulate(array.begin(), array.begin()+i, 0);
      s2 = accumulate(array.begin()+i, array.end(), 0);
      if (s1 - s2 > 0) {
        diff = s1 - s2;
      } else {
        diff = s2 - s1;
      }

      //First iteration
      if (i==0) {
        min = diff;
      } else {
        if (diff < min) {
          min = diff;
        }
      }

    }

    printf("%d", min);

    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3


def powerset(iterable):
    for mask in range(2 ** len(iterable)):
        yield {elem for i, elem in enumerate(iterable) if mask >> i & 1}

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    h, w, k = map(int, input().split())
    c = [input() for _ in range(h)]
    ans = 0
    for ys in powerset(range(h)):
        for xs in powerset(range(w)):
            count = 0
            for y in set(range(h)) - ys:
                for x in set(range(w)) - xs:
                    if c[y][x] == "#":
                        count += 1
            if count == k:
                ans += 1
    print(ans)

if __name__ == "__main__":
    main()


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

void init() {
//#if __GLIBCXX__ == 20160609
#ifdef FIRE_MIND
    freopen("a.in", "r", stdin);
    ///freopen("a.out", "w", stdout);
#else
    ///freopen(TASKNAME".in", "r", stdin);
    ///freopen(TASKNAME".out", "w", stdout);
#endif
}

typedef long long ll;
typedef long double ld;

const double EPS = 1e-9;
const int INF = (int)1e9 + 41;
const int N = (int)2e6 + 7;

bitset<N> u;
int n;
int a[N];

int main() {
    init();

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

    u[0] = 1;
    for (int i = 0; i < n; i++) {
        u = (u | (u << a[i]));
    }

    int ps = -1;
    for (int i = 0; i <= sum / 2; i++) {
        if (u[i])
            ps = i;
    }

    cout << sum - ps;

    return 0;
}


Measured memory_bytes: 1280
#include <algorithm>
#include <cmath>
#include <iostream>
#include <limits>
#include <numeric>
#include <string>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
using namespace std;
int main() {
  ll n, y, x_s, y_s, z_s;
  cin >> n >> y;
  x_s = y / 10000;

  rep(x_s, n + 1) {
    rep(y_s, n - x_s + 1) {
      z_s = n - x_s - y_s;
      if (z_s >= 0) {
        if (x_s + y_s + z_s == n &&
            10000 * x_s + 5000 * y_s + z_s * 1000 == y) {
          cout << x_s << " " << y_s << " " << z_s << endl;
          return 0;
        }
      }
    }
  }
  cout << "-1 -1 -1" << endl;
}

Measured memory_bytes: 3664
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>

int N;
std::vector<long long int> a;

int main(void){
    std::cin >> N;
    a.resize(N);
    for(int i=0; i<N; ++i){
        std::cin >> a[i];
    }

    long long int left  = a[0];
    long long int right = 0;
    for(int i=1; i<N; ++i){
        right += a[i];
    }

    long long int ans = (left < right) ? right-left : left-right;
    for(int i=1; i<N-1; ++i){
        left  += a[i];
        right -= a[i];

        long long int diff = (left<right) ? right - left : left-right;
        ans = (ans > diff) ? diff : ans;
    }

    std::cout << ans << std::endl;
}


Measured memory_bytes: 1792
#include <iostream>
#include <cstdio>
using namespace std;
int main(void) {
  char in[9];
  while(scanf("%s", in) != EOF) {
    if(in[0] == 'o' && in[1] == 'o' && in[2] == 'o') cout << 'o' << endl;
    else if(in[3] == 'o' && in[4] == 'o' && in[5] == 'o') cout << 'o' << endl;
    else if(in[6] == 'o' && in[7] == 'o' && in[8] == 'o') cout << 'o' << endl;
    else if(in[0] == 'o' && in[3] == 'o' && in[6] == 'o') cout << 'o' << endl;
    else if(in[1] == 'o' && in[4] == 'o' && in[7] == 'o') cout << 'o' << endl;
    else if(in[2] == 'o' && in[5] == 'o' && in[8] == 'o') cout << 'o' << endl;
    else if(in[0] == 'o' && in[4] == 'o' && in[8] == 'o') cout << 'o' << endl;
    else if(in[2] == 'o' && in[4] == 'o' && in[6] == 'o') cout << 'o' << endl;

    else if(in[0] == 'x' && in[1] == 'x' && in[2] == 'x') cout << 'x' << endl;
    else if(in[3] == 'x' && in[4] == 'x' && in[5] == 'x') cout << 'x' << endl;
    else if(in[6] == 'x' && in[7] == 'x' && in[8] == 'x') cout << 'x' << endl;
    else if(in[0] == 'x' && in[3] == 'x' && in[6] == 'x') cout << 'x' << endl;
    else if(in[1] == 'x' && in[4] == 'x' && in[7] == 'x') cout << 'x' << endl;
    else if(in[2] == 'x' && in[5] == 'x' && in[8] == 'x') cout << 'x' << endl;
    else if(in[0] == 'x' && in[4] == 'x' && in[8] == 'x') cout << 'x' << endl;
    else if(in[2] == 'x' && in[4] == 'x' && in[6] == 'x') cout << 'x' << endl;
    
    else cout << 'd' << endl;
  }
  return 0;
}

Measured memory_bytes: 0
#include<stdio.h>
int dp[1002][1002]={0},a[1001],b[1001];
int main(){
	int n,k,i,j,x,y,z,min;
	scanf("%d %d",&n,&k);
	for(i=0;i<n;i++)scanf("%d",&a[i]);
	for(i=0;i<k;i++)scanf("%d",&b[i]);
	for(i=0;i<n+1;i++){
		for(j=i;j<k+1;j++){
			if(dp[i][j+1]==0 || dp[i][j+1]>dp[i][j])dp[i][j+1]=dp[i][j];
			if(dp[i+1][j+1]==0 || dp[i+1][j+1]>dp[i][j]+a[i]*b[j])dp[i+1][j+1]=dp[i][j]+a[i]*b[j];
		}
	}
	printf("%d\n",dp[n][k]);
	return 0;
}


Measured memory_bytes: 4912
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ld long double
#define pb push_back
 
#define sec second
#define fir first
#define mo 1000000007
#define inf 1e18
#define rep(i, s, n) for (ll i = s; i < n; i = i + 1)
#define rrep(i,s,n) for(ll i=s;i>=n;i--)

ll mod(ll n) { return (n % (ll)mo + (ll)mo)%(ll)mo;}

int main(){
	ll x;
	cin>>x;
	string c = (x>=30) ?"Yes" : "No" ;
	cout<<c;
}
		 

Measured memory_bytes: 3624
import collections
n = int(input())
a = list(map(int,input().split()))
c = collections.Counter(a)
sumnum = 0
for key,value in c.items():
    if value >= 2:
        sumnum += value*(value-1)//2

for i in range(n):
    key = [a[i]]
    ans = sumnum
    value = c[a[i]]
    if value >= 3:
        ans -= value*(value-1)//2
        ans += (value-2)*(value-1)//2
    if value <= 2:
        ans -= value*(value-1)//2
    print(ans)

Measured memory_bytes: 26780
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define lo long long 
#define inf 1000000000
#define md 1000000007
#define pb push_back
#define li 100005
using namespace std;
int n,m,vis[li],x,y,cev,deg[li];
int main(){
	vis[1]=1;
	scanf("%d %d",&n,&m);
	for(int i=2;i<=n;i++) deg[i]=1;
	for(int i=1;i<=m;i++){
		scanf("%d %d",&x,&y);
		if(vis[x]>0){
			vis[y]++;
			if(deg[x]>0) deg[x]--;
			else
				vis[x]--;
		}
		else{
			if(deg[x]>0) {deg[x]--;deg[y]++;}
		}
	}
	for(int i=1;i<=n;i++){
		if(vis[i]>0){
			cev++;
		}
	}
	printf("%d\n",cev);
	return 0;
}


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


//defines...
#define ll long long
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define mp make_pair
#define in insert
#define pi 2*acos(0.0)1
#define srt(s) sort(s.begin(),s.end())
#define rsrt(s) sort(s.rbegin(),s.rend())
#define all(x) x.begin(),x.end()

const ll mod=1e9+7;
const ll MX=2e5+5;

//code goes from here...



int main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);

    freopen("output.txt", "w", stdout);
#endif

    boost
    //---------------------------------
    int n;
    cin >> n;
    
    cout << !n << endl;
    
    //---------------------------------
    
    return 0;
}


Measured memory_bytes: 3644
#include<bits/stdc++.h>
    using namespace std;
     
    #define       pb(a)             push_back((a))
    #define       mp(a,b)           make_pair((a),(b))
    #define       REP(a,b)          for(ll i=(a);i<(b);i++)
    #define       REP2(a,b)         for(ll j=(a);j<(b);j++)
    #define       REPE(a,b,c,d)     REP(a,b)for(ll j=(c);j<(d);j++)
    #define       REPV(a,b,c)       for(ll (a)=b;(a)<(c);(a)++)
    #define       IREP(a,b)         for(ll i=(a);i>=(b);i--)
    #define       IREP2(a,b)        for(ll j=(a);j>=(b);j--)
    #define       IREPV(a,b,c)      for(ll (a)=b;(a)>=(c);(a)--)
    #define       all(v)            (v).begin(),(v).end()
    #define       Trvs(c)           for (auto &it :c)
    #define       INF               INT_MAX
    #define       sz(x)             x.size()
    #define       flash             ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    #define       F                 first
    #define       S                 second
    #define       MOD               1000000007

    using         ll     = long long;
    using         vll    = vector<ll>;
    using         vvll   = vector<vll>;
    using         pll    = pair<ll, ll>;
    using         vpll   = vector<pll>;
    using         vvpll  = vector<vpll>;
     


void solve(){
	string a, b, c; cin >> a >> b;
	ll x,y; cin>> x >> y;
	cin >> c; 
	if(c==a)x--;
	else y--;
	cout<<x<<" " <<y;
}
	

     
    	
int main(){
    	flash
    	
    	
    	// ll t;cin>>t;while(t--)
    	solve();
    	return 0;
    } 	

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

int main()
{
  int A, B, K, C[100], j = 0;
  
  cin >> A >> B >> K;

  for(int i = 1; i <= min(A, B); i++){
    if(A % i == 0 && B % i == 0)
      C[j++] = i;
  }

  cout << C[j - K] << endl;
  return 0;
}


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

int main()
{
    int N, T, A;
    cin >> N >> T >> A;
    int min = 1 << 30, num;
    for (int i = 0; i < N; i++)
    {
        int H;
        cin >> H;
        int d = T * 1000 - H * 6 - A * 1000;
        if (d < 0)
        {
            d = -d;
        }
        if (d < min)
        {
            min = d;
            num = i + 1;
        }
    }
    cout << num << endl;
}

Measured memory_bytes: 3632
#include<stdio.h>

int main(){
  int x[31];
  int w,n,a,b,temp,i;
  
  scanf("%d",&w);
  for(i=1;i<=w;i++){
    x[i]=i;
  }
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d,%d",&a,&b);
    temp=x[a];
    x[a]=x[b];
    x[b]=temp;
  }
  for(i=1;i<=w;i++){
    printf("%d\n",x[i]);
  }
  return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<functional>
#include<queue>
#include <iomanip>
#include<map>
#include<limits>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<utility>
#include<complex>
#include<cstdlib>
#include<set>
#include<cctype>

#define DBG cerr << '!' << endl;
#define REP(i,n) for(int (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(int (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(int (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int i = 0;i < (n);i++)cerr << v[i] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()

using namespace std;

typedef long long ll;
typedef vector<int> iv;
typedef vector<iv> iiv;
typedef vector<string> sv;

char mp[2][3];

int main()
{
	REP(i,2)REP(j,3)cin >> mp[i][j];
	
	if(mp[0][0] == mp[1][2] &&
		mp[0][1] == mp[1][1] &&
		mp[0][2] == mp[1][0])
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
	
	return 0;
}

Measured memory_bytes: 256
n = int(input())
ans = 0
a = n // 15
mod15 = n % 15
for i in range(a):
    ans += (120 * i) + 60
for i in range(a*15+1, n+1):
    if (i % 3 != 0) and (i % 5 != 0):
        ans += i
print(ans)


Measured memory_bytes: 9172
S = list(map(int, input()))
N = len(S)

def solve(c):
	cond = 0
	f = [0] * N
	if S[0] == 1:
		f[0] = 1
	cnt = 1
	for i in range(1,N-c+1):
		if i < c:
			f[i] = f[i-1]
			if (S[i] + f[i]) % 2 == 1:
				f[i] += 1
			cnt += 1

		if i >= c:
			f[i] = f[i-1] - f[i-c]
			if (S[i] + f[i]) % 2 == 1:
				f[i] += 1
			cnt += 1
		
		if cnt >= c:
			cond = 1
			break
	if cond == 0:
		for i in range(N-c+1,N):
			f[i] = f[i-1] - f[i-c]
			if (S[i] + f[i]) % 2 == 0:
				cnt += 1
			else:
				break

			if cnt >= c:
				cond = 1
				break

	return cond

def binary_search(s,f):
	if s == f:
		return s
	elif s+1 == f:
		if solve(f):
			return f
		else:
			return s

	c = (s+f)//2

	if solve(c):
		return binary_search(c,f)
	else:
		return binary_search(s,c)

print(binary_search(1,N))

Measured memory_bytes: 7308
import java.util.Scanner;

public class Main {

	static boolean f(int w, int[] book, int n, int m) {
		int need = 0;
		int s = w;
		int i = 0;
		while (i != m) {
			if (need == n)
				return false;
			if (s - book[i] >= 0) {
				s -= book[i];
				i++;
			} else {
				s = w;
				need++;
			}
		}
		return true;
	}

	public static void main(String[] args) {

		Scanner scanner = new Scanner(System.in);
		while (true) {
			int n = scanner.nextInt();
			int m = scanner.nextInt();
			if (n == 0 && m == 0)
				break;
			int[] book = new int[m];
			int r = 0;
			for (int i = 0; i < m; i++) {
				book[i] = scanner.nextInt();
				r += book[i];
			}
			int l = r / n;

			while (r - l > 1) {
				int mid = (l + r) / 2;
				if (f(mid, book, n, m)) {
					r = mid;
				} else {
					l = mid;
				}
			}
			System.out.println(f(l, book, n, m) ? l : r);
		}

	}
}

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

using namespace std;

int ans=INT_MAX;

void calc(int arr[15][15],int c[15],int i,int n,int m,int sum[15],int price,int x){
    if(i==n){
        int k=0;
        while(k<m){
            if(sum[k]<x){
                break;
            }
            k++;
        }
        if(k==m){
            ans=min(ans,price);
        }
        return;
    }
    calc(arr,c,i+1,n,m,sum,price,x);
    price+=c[i];
    for(int k=0;k<m;k++){
        sum[k]+=arr[i][k];
    }
    calc(arr,c,i+1,n,m,sum,price,x);
    price-=c[i];
    for(int k=0;k<m;k++){
        sum[k]-=arr[i][k];
    }
}

int main(){
    int n,m,x,c[15],arr[15][15],sum[15]={0},price=0;
    cin>>n>>m>>x;
    for(int i=0;i<n;i++){
        cin>>c[i];
        for(int j=0;j<m;j++){
            cin>>arr[i][j];
        }
    }
    calc(arr,c,0,n,m,sum,price,x);
    if(ans==INT_MAX){
        cout<<"-1";
    }
    else{
        cout<<ans;
    }
}

Measured memory_bytes: 3636
<?php
fscanf(STDIN, "%d", $N);
$d = explode(" ", fgets(STDIN));
echo solve1($d);

function solve1($x) {
    $cnt = count($x);
    $ret = 0;
    for ($i = 0; $i < $cnt - 1; $i++) {
        for ($j = $i + 1; $j < $cnt; $j++) {
            $ret += $x[$i] * $x[$j];
        }
    }
    return $ret;
}

function solve2($x) {
    $sum = array_sum($x);
    $ret = 0;
    foreach ($x as $y) {
        $ret += ($sum - $y) * $y;
    }
    return $ret / 2;
}


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

using namespace std;
#define DEBUG
#ifdef DEBUG
#define dump(x) cout << "[*] " #x ": " << x << endl
#define debug(x) x
#else
#define dump(x)
#define debug(x)
#endif

#define int long long
typedef long long ll;
//constexpr int INF = 1e9;
//constexpr int MOD = 1000000007;

decltype(1) main() {
    //cin.tie(nullptr);
    //ios_base::sync_with_stdio(false);
    string s;
    cin >> s;
    if (s[2] == s[3] && s[4] == s[5]) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#
# abc122 b
#
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """ATCODER"""
        output = """3"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """HATAGAYA"""
        output = """5"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """SHINJUKU"""
        output = """0"""
        self.assertIO(input, output)


def resolve():
    S = input()

    ans = 0
#    for i in range(len(S)):
#        t = 0
#        if S[i] == "A" or S[i] == "C" or S[i] == "G" or S[i] == "T":
#            t += 1
#            for j in range(i+1, len(S)):
#                if S[j] == "A" or S[j] == "C" or S[j] == "G" or S[j] == "T":
#                    t += 1
#                else:
#                    break
#        ans = max(ans, t)

    ans = 0
    for i in range(len(S)):
        for j in range(i+1, len(S)+1):
            if S[i:j].count("A") + S[i:j].count("C") + S[i:j].count("G") + S[i:j].count("T") == len(S[i:j]):
                ans = max(ans, len(S[i:j]))
    print(ans)


if __name__ == "__main__":
    # unittest.main()
    resolve()


Measured memory_bytes: 16036
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <iomanip>
#include <queue>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;

int a;
string s;

int main(){
    cin>>a>>s;

    if(a>=3200){
        cout<<s<<endl;
    }else{
        cout<<"red"<<endl;
    }
}

Measured memory_bytes: 256
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<functional>
#include <random>
#include<iostream>
using namespace std;

/*
(奇数)*a_k/2の形で書かれる数が「半倍数」である。
普通にa_k/2たちの最小公倍数 L を求めて、それがすべてのa_kの半倍数であれば、(奇数)*Lの形の数の個数を出力すればよい。
それ以外なら0である。
*/

long long LCM(long long a, long long b) {
	long long GCM;
	long long a_copy = a;
	long long b_copy = b;
	if (a%b == 0) {
		return a;
	}
	while (a % b != 0) {
		GCM = a % b;
		a = b;
		b = GCM;
	}
	return a_copy * b_copy / GCM;
}

int main() {
	long long N, M;
	long long a[100000];

	cin >> N >> M;


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

	long long L;
	/*とりあえず最小半倍数(の候補)を求めていく。途中でMを超えたらその時点で0を出力しておわり*/
	L = a[0] / 2;
	for (int i = 1; i < N; i++) {
		L = LCM(L, a[i] / 2);
		if (L > M) {
			cout << "0\n";
			return 0;
		}
	}
	/*ほんとうに半倍数？*/
	for (int i = 0; i < N; i++) {
		if ((L / (a[i] / 2)) % 2 == 0) {
			cout << "0\n";
			return 0;
		}
	}

	cout << (M / L) - (M / (2*L)) << "\n";

}

Measured memory_bytes: 1024
use proconio::input;

use num;
use std::convert;
pub fn mpow<Output, Base, Exponent>(base: Base, exponent: Exponent, modvalue: Output) -> Output
where
    Output: num::Integer + Copy + convert::From<Base> + convert::From<Exponent>,
    Base: num::Integer,
    Exponent: num::Integer,
{
    let mut result: Output = Output::one();
    let two: Output = From::from(Exponent::one() + Exponent::one());
    let mut mm: Output = From::from(exponent);
    let mut nn: Output = From::from(base);
    while !mm.is_zero() {
        if mm.is_odd() {
            result = (result * nn) % modvalue;
        }
        nn = (nn * nn) % modvalue;
        mm = mm / two;
    }
    result
}

#[proconio::fastout]
fn main() {
    input! {
        n: i32
    }

    let m: i64 = 1000000007;
    let ans10: i64 = mpow(10, n, m);
    let ans9: i64 = mpow(9, n, m);
    let ans8: i64 = mpow(8, n, m);
    let ans = (ans10 + (m - ans9) * 2 + ans8) % m;
    println!("{}", ans);
}


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

using namespace std;
int deg[100005],n,m,res;
vector <int> a[100005];
int d[100005];
int vs[100005];
void dfs(int u)
{
    vs[u]=1;
    for(int j=0; j<a[u].size(); j++)
    {
        int v=a[u][j];
        if(vs[v]==0)
            dfs(v);
        d[u]=max(d[u],d[v]+1);
        res=max(d[u],res);
    }
    if(a[u].empty())
        d[u]=0;
}
int main()
{
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int u,v;
        cin>>u>>v;
        a[u].push_back(v);
        deg[v]++;
    }
    for(int i=1; i<=n; i++)
        if(vs[i]==0)
            dfs(i);

    cout<<res;

}


Measured memory_bytes: 8960
import collections
import sys
input=sys.stdin.readline

n,k=map(int,input().split())
l=list(map(int,input().split()))
#print(l)
s=collections.Counter(l)
s=s.most_common()
#print(s)
a=0
for i in range(k,len(s)):
    a+=s[i][1]
print(a)

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

#define rep(i,s,n) for (int i = (int)s; i < (int)n; i++)
#define ll long long
#define ld long double
#define pb push_back
#define eb emplace_back
#define All(x) x.begin(), x.end()
#define Range(x, i, j) x.begin() + i, x.begin() + j
#define lbidx(x, y) lower_bound(x.begin(), x.end(), y) - x.begin()
#define ubidx(x, y) upper_bound(x.begin(), x.end(), y) - x.begin()
#define llbidx(x, y, z) lower_bound(x.begin(), x.end(), z) - lower_bound(x.begin(), x.end(), y) // 二要素間の距離
#define deg2rad(deg) ((((double)deg)/((double)360)*2*M_PI))
#define rad2deg(rad) ((((double)rad)/(double)2/M_PI)*(double)360)
#define Find(set, element) set.find(element) != set.end()
#define Decimal(x) printf("%.10f\n", x) // 小数点を10桁まで表示
// debug用
#define PrintVec(x) for (auto elementPrintVec: x) { cout << elementPrintVec << " "; } cout << "\n";
#define debug(x) cerr << #x << ": " << (x) << "\n";
#define endl "\n"
// gcj print用
#define Case(x) printf("Case #%d: ", x);

typedef pair<int, int> PI;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<int>>> vvvl;
typedef vector<PI> vpi;
typedef vector<vector<PI>> vvpi;
typedef vector<vector<vector<PI>>> vvvpi;
typedef vector<PLL> vpl;
typedef vector<vector<PLL>> vvpl;
typedef vector<vector<vector<PLL>>> vvvpl;

int POWINT(int x, int n) {
  int ret = 1;
  while (n > 0) {
    if (n & 1) ret *= x;
    x *= x;
    n >>= 1;
  }
  return ret;
};

ll POWLL(ll x, int n) {
  ll ret = 1;
  while (n > 0) {
    if (n & 1) ret *= x;
    x *= x;
    n >>= 1;
  }
  return ret;
};

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

void print() {
  cout << endl;
}

template <class T>
void print(vector<T> &vec) {
  for (auto& a : vec) {
    cout << a;
    if (&a != &vec.back()) cout << " ";
  }
  cout << endl;
}

template <class T>
void print(vector<T> &vec, ll k){
   ll n = vec.size();
   k = min(k, n);
   rep(i, 0, k-1) cout << vec[i] << " ";
   cout << vec[k-1] << endl;
}

template <class T>
void print(vector<vector<T>> &df) {
  for (auto& vec : df) {
    print(vec);
  }
}

template<class T, class U>
void print(pair<T,U> &p){
  cout << p.first << " " << p.second << "\n";
}

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

  string S;
  cin >> S;

  char last = S[S.size()-1];

  if (last == '3') {
    cout << "bon" << endl;
  } else if (last == '0' || last == '1' || last == '6' || last == '8') {
    cout << "pon" << endl;
  } else {
    cout << "hon" << endl;
  }

  return 0;
};


Measured memory_bytes: 3644
use proconio::input;
use std::f64::consts::PI;

fn main() {
    input! {
        a: f64,
        b: f64,
        h: f64,
        m: f64,
    }

    solve(a, b, h, m);
}

fn solve(a: f64, b: f64, h: f64, m: f64) {
    let alpha = 2.0 * PI * h / 12.0 + 2.0 * PI * m / (60.0 * 12.0);
    let beta = 2.0 * PI * m / 60.0;
    let gamma = (alpha - beta).abs();

    let cc = a * a + b * b - 2.0 * a * b * gamma.cos();
    println!("{}", cc.sqrt());
}


Measured memory_bytes: 3004
s = input()
k = int(input())

n = len(s)
strs = set([])

for i in range(n):
    for j in range(i+1, min(i+k+1,n+1)):
        strs.add(s[i:j])
strs = list(strs)
strs.sort()
print(strs[k-1])


Measured memory_bytes: 39920
#include <bits/stdc++.h>
typedef long long ll;
const int INF = 1e9,MOD = 1e9+7,ohara = 1e6;
const ll LINF = 1e18;
using namespace std;

#define rep(i,n) for(ll (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(ll i=(a);i<(b);i++)
#define rrrep(i,a,b) for(ll i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl

ll n,cnt=0,ans[ohara],a,b,c,d,cmp,cmpp,m,h,w,x,sum=0,pos,p[ohara],y[ohara];
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};

//-------------------------↓↓↓↓↓↓------------------------

int main(void){
       cin.tie(0);
    ios::sync_with_stdio(false);
      
    cin>>n>>m;
    pair<ll,ll> data[ohara];
    map<pair<ll,ll>,ll> ac;
    rep(i,m){
        cin>>p[i]>>y[i];
        ac[{p[i],y[i]}]=i;
        data[i]=make_pair(y[i],p[i]);
        //cout<<data[i].second.second<<"\n";
    }
    sort(data,data+m);
    map<ll,ll> cou;
    rep(i,m){
        cou[data[i].second]++;
        ans[ac[{data[i].second,data[i].first}]]=cou[data[i].second];
        //cout<<data[i].first<<" "<<data[i].second<<" "<<ac[{data[i].second,data[i].first}]<<"\n";
    }
    //rep(i,m)Cout(ans[i]);
    rep(i,m){
        s=to_string(p[i]);
        rep(j,6-Size(s))cout<<"0";
        cout<<p[i];
        s=to_string(ans[i]);
        rep(j,6-Size(s))cout<<"0";
        cout<<ans[i]<<"\n";
    }
    return 0;
    
}


Measured memory_bytes: 38656
package main

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

// 文字列を1行取得
func StrStdin() (stringReturned string) {
    scanner := bufio.NewScanner(os.Stdin)

    scanner.Scan()
    stringInput := scanner.Text()

    stringReturned = strings.TrimSpace(stringInput)
    return
}

func main(){
  var s = StrStdin()
  // fmt.Println(s)
  result := 0
  for i:=0; i<len(s); i++ {
    // fmt.Println(s[i:i+1])
    if s[i:i+1] == "1"{
      result+=1
    }
  }
  fmt.Println(result)
}


Measured memory_bytes: 640
while True:

    a, b = input().split()

    if a == "0" and b == "0":
        break

    a1 = 0
    a2 = 0

    for i in range(4):
        if a[i] == b[i]:
            a1 += 1

    for i in range(4):
        for j in range(4):
            if a[i] == b[j]:
                a2 += 1

    print(a1, a2-a1)



Measured memory_bytes: 5572
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
#include <queue>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
const int INF = 1<<29;

vector<int> eratosthenes(int n) {
  vector<int> v(n);
  for (int i=2; i<n; i++) v[i] = i;
  for (int i=2; i*i<n; i++)
    if (v[i])
      for (int j=i*i; j<n; j+=i)
        v[j] = 0;
  return v;
}

int main() {
  vector<int> prime = eratosthenes(1000000);
  vector<int> psum(2000000);
  int sum = 0;
  REP(i,1000000) {
    if (prime[i]) ++sum;
    psum[i] = sum;
  }
  int n;
  while(cin >> n, n) {
    int res = 0;
    REP(i,n) {
      int p, m;
      cin >> p >> m;
      
      int ue = min(999983, p+m);
      int shita = max(0, p-m-1); 
      int X = psum[ue] - psum[shita];
      // cout << ue << " " << psum[ue] << endl;
      // cout << shita << " " << psum[shita] << endl;
      if (X)
        res += X-1;
      else
        --res;
    }
    cout << res << endl;
  }
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll X, K, D;

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> X >> K >> D;
	
	X = abs(X);
	ll move2zero = X/D;
	if (move2zero >= K) cout << X - K*D;
	else {
		X -= D*move2zero;
		if (abs(move2zero - K) % 2 == 1){
			ll ans = min(abs(X + D),abs(X - D));
			cout << ans;
		}
		else cout << X;
	}
	return 0;
}

Measured memory_bytes: 3652
#include <stdio.h>

int main(int argc, const char * argv[]) {
    int a[10];
    int i, n = 0;
    
    while (scanf("%d", &i) != EOF) {
        if(i != 0) {
            a[n++] = i;
        } else {
            printf("%d\n",a[--n]);
        }
    }
    return 0;
}

Measured memory_bytes: 600
import collections
n = int(input())
s = [input() for _ in range(n)]
c = collections.Counter(s)
a = c.most_common()
max = a[0][1]
a.sort(key=lambda x: x[0])
for i in range(len(a)):
    if a[i][1]==max:
        print(a[i][0])

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

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvvi = vector<vector<vector<int>>>;
using mii = map<int, int>;
using msi = map<string, int>;
using pii = pair<int, int>;

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

    int n;
    cin >> n;
    vi a(n);
    REP(i, n) cin >> a[i];
    sort(a.begin(), a.end());
    
    ll ans = 0;
    if(n % 2 == 0) {
        ll sum = 0;
        REP(i, n / 2 - 1) sum -= 2 * a[i];
        sum += -a[n / 2 - 1] + a[n / 2];
        FOR(i, n / 2 + 1, n) sum += 2 * a[i];
        cout << sum << endl;
        return 0;
    }
    // nが奇数
    ll sum = 0;
    REP(i, (n-1) / 2) sum -= 2 * a[i];
    sum += a[(n-1)/2] + a[(n+1)/ 2] ;
    FOR(i, (n+1)/2 + 1, n) sum += 2 * a[i];
    ans = sum;
    
    sum = 0;
    REP(i, (n-3) / 2) sum -= 2 * a[i];
    sum -= a[(n-3)/2] + a[(n-1)/ 2] ;
    FOR(i, (n-1)/2 + 1, n) sum += 2 * a[i];   
    ans = max(ans, sum);
    cout << ans << endl;


    return 0;
}

Measured memory_bytes: 640
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
	w,h = readline() |> split |> parseMap
	p = Tuple{Int,Int}[(0,0) for i in 1:w+h]
	for i in 1:w
		p[i] = (readline()|>parseInt,0)
	end
	for i in 1:h
		p[w+i] = (readline()|>parseInt,1)
	end
	p = sort(p,by=x->x[1])
	ps = 0
	qs = 0
	ans = 0
	if p[1][2]==0
		ans += p[1][1]*(h+1)
		ps += 1
	else
		ans += p[1][1]*(w+1)
		qs += 1
	end
	for i in 2:h+w
		if p[i][2]==0
			ans += p[i][1]*(h+1-qs)
			ps += 1
		else
			ans += p[i][1]*(w+1-ps)
			qs += 1
		end
	end
	println(ans)
end

main()

Measured memory_bytes: 150068
my $x = <>;
chomp($x);

my $count = 0;
my $ss = 0;
for my $i (0..length($x)-1) {
    my $c = substr($x, $i, 1);
    if ($c eq 'S') {
        ++$ss;
    } elsif ($c eq 'T') {
        if ($ss == 0) {
            ++$count;
        } else {
            --$ss;
        }
    }
}
print $count + $ss, "\n";

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

int main (int argc,char **argv)
{
	char x[4],y[4];
	
	scanf("%s %s",x,y);

	
	if((x[0] == y[2])&&(x[1] == y[1])&&(x[2] == y[0]))
	{
		printf("YES\n");
	}
	
	else 
	{
		printf("NO\n");
	}

	return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
#include <stdlib.h>
#define MAX 2000001
#define VMAX 10000
int main()
{
  unsigned short *A,*B;
  int n,C[VMAX+1],i,j;
  scanf("%d",&n);
  A = malloc(sizeof(short)*n+1);
  B = malloc(sizeof(short)*n+1);
  for(i=0;i<=VMAX;i++)
  {
    C[i]=0;
  }
  for(i=0;i<n;i++)
  {
    scanf("%hu",&A[i+1]);
    C[A[i+1]]++;
  }
  for(i=1;i<=VMAX;i++)
  {
    C[i] = C[i] + C[i-1];
  }
  for(j=1;j<=n;j++)
  {
    B[C[A[j]]]=A[j];
    C[A[j]]--;
  }
  for(i=1;i<=n;i++)
  {
    printf("%d",B[i]);
    if(i!=n)
    printf(" ");
  }
  printf("\n");
  return 0;
}



Measured memory_bytes: 9620
// -*- mode:c++; coding:utf-8; indent-tabs-mode:nil; -*-
// ALDS1_2-C
  
#include <cstring>
#include <iostream>
 
struct card {
  char mark;
  unsigned int number;
};
 
static void print_cards(const card cards[], const unsigned int n) {
  const char* sep = "";
  for (unsigned int i = 0; i < n; ++i) {
    const card* const cardp = &cards[i];
    std::cout << sep << cardp->mark << cardp->number;
    sep = " ";
  }
  std::cout << std::endl;
}
 
static void swap(card* a, card* b) {
  card tmp = *a;
  *a = *b;
  *b = tmp;
}
 
void bubble_sort(card cards[], const unsigned int n) {
  for (unsigned int j = 0; j < n-1; ++j) {
    for (unsigned int i = n-1; i > j; --i) {
      if (cards[i-1].number > cards[i].number) {
        swap(&cards[i-1], &cards[i]);
      }
    }
  }
}
  
void selection_sort(card cards[], const unsigned int n) {
  for (unsigned int i = 0; i < n-1; ++i) {
    unsigned int min_j = i;
    for (unsigned int j = i+1; j < n; ++j) {
      if (cards[min_j].number > cards[j].number) {
        min_j = j;
      }
    }
    if (i != min_j) {
      swap(&cards[i], &cards[min_j]);
    }
  }
}
  
int main(void) {
  unsigned int n;
  std::cin >> n;
  card cards1[n], cards2[n];
  for (unsigned int i = 0; i < n; ++i) {
    std::cin >> cards1[i].mark;
    std::cin >> cards1[i].number;
  }
  std::memcpy(cards2, cards1, sizeof(cards1));
 
  bubble_sort(cards1, n);
  print_cards(cards1, n);
  std::cout << "Stable" << std::endl; // bubble sort is stable
 
  selection_sort(cards2, n);
  print_cards(cards2, n);
  if (std::memcmp(cards1, cards2, sizeof(cards1)) == 0) {
    std::cout << "Stable" << std::endl;
  } else {
    std::cout << "Not stable" << std::endl;
  }
 
  return 0;
}
// end

Measured memory_bytes: 1164
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define MAXN 10005
#define MAXM 20005
struct Edge
{
	int id,len,cos;
	int nxt;
	Edge(){}
	Edge(int i,int l,int c){id=i;len=l;cos=c;}
}E[2*MAXM];
int V[MAXN],cur;
void add_edge(int u,int v,int length,int cost)
{
	E[cur]=Edge(v,length,cost);
	E[cur].nxt=V[u];
	V[u]=cur;
	cur++;
	E[cur]=Edge(u,length,cost);
	E[cur].nxt=V[v];
	V[v]=cur;
	cur++;
}
int N,M;
int dis[MAXN],cost[MAXN];
bool inque[MAXN];
queue<int>Q;
int SPFA()
{
	memset(inque,0,sizeof inque);
	for(int i=1;i<=N;i++)
		dis[i]=cost[i]=0x3FFFFFFF;
	while(!Q.empty())
		Q.pop();
	Q.push(1);
	dis[1]=0;
	inque[1]=1;
	cost[1]=0;
	while(!Q.empty())
	{
		int t=Q.front();
		Q.pop();
		inque[t]=0;
		for(int p=V[t];p!=-1;p=E[p].nxt)
		{
			int to=E[p].id;
			int len=E[p].len;
			if(dis[to]>dis[t]+len||(dis[to]==dis[t]+len&&cost[to]>E[p].cos))
			{
				dis[to]=dis[t]+len;
				cost[to]=E[p].cos;
				if(!inque[to])
				{
					Q.push(to);
					inque[to]=1;
				}
			}
		}
	}
	int ret=0;
	for(int i=1;i<=N;i++)
		ret+=cost[i];
	return ret;
}
int main()
{
	int u,v,d,c;
	while(~scanf("%d%d",&N,&M))
	{
		if(!N&&!M)break;
		memset(V,-1,sizeof V);
		cur=0;
		for(int i=1;i<=M;i++)
		{
			scanf("%d%d%d%d",&u,&v,&d,&c);
			add_edge(u,v,d,c);
		}
		printf("%d\n",SPFA());
	}
	return 0;
}

Measured memory_bytes: 3316
#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string>
#include <assert.h>
#include <ctype.h>
#include <limits.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <bitset>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <sstream>
using namespace std;


int main()

{
	int n;
	cin >> n;
	vector<int>arr(n + 1);

	for (int i = 1;i <= n;i++)
		cin >> arr[i];
	int count = 0;
	if (arr[1] == 1) {
		swap(arr[1], arr[2]);
		count++;
	}
	for (int i = 2;i < n;i++)
	{
		if (arr[i] == i)
			if (arr[i - 1] == i - 1)
			{
				swap(arr[i - 1], arr[i]);
				count++;
			}
			else
			{
				swap(arr[i + 1], arr[i]);
				count++;
			}
	}

	if (arr[n] == n)
	{
		swap(arr[n], arr[n - 1]);
		count++;
	}

	cout << count;
	
		return 0;
}


Measured memory_bytes: 640
#include <stdio.h>
 
#define N 100000
typedef struct {
  char mark;
  int num;
  int s;
}Card;
 
void quickSort(Card *A,int p,int r){
  int q;
   
  if(p<r){
    q = partition(A,p,r);
    quickSort(A,p,q-1);
    quickSort(A,q+1,r);
  }
}
 
int partition(Card *A,int p,int r){
 
  int i,j,x;
  Card temp;
   
  x=A[r].num;
  i=p-1;
 
   for(j=p; j<r; j++){
     if (A[j].num <= x){
     i=i+1;
     temp = A[i];
     A[i]=A[j];
     A[j]=temp;
     }
   }
   temp=A[i+1];
   A[i+1]=A[r];
   A[r]=temp;
  
   return i+1;
 }
  
 int main(){
  
   int i,j,n,p=0,r,flag=0;
   char c;
   Card A[N];
  
   scanf("%d%c",&n,&c);
  
   for(i=0; i<n; i++){
     scanf("%c%d%c",&A[i].mark,&A[i].num,&c);
     A[i].s=i;
   }
  
   r=n-1;
    
   quickSort(A,p,r);
  
   for(i=0;i<r-1;i++){
     if(A[i].num == A[i + 1].num && A[i].s > A[i + 1].s){
       printf("Not stable\n");
       flag = 1;
       break;
     }
   }
  
   if(flag==0) printf("Stable\n");
  
     
   for(i=0; i<n; i++){
     printf("%c %d\n",A[i].mark,A[i].num);
   }
    
   return 0;
 }

Measured memory_bytes: 1780
from heapq import *
n,m = map(int,input().split())
l = [[] for i in range(m+1)]
for i in range(n):
  a,b = map(int,input().split())
  if a < m+1:
    l[a].append(b)

ans = 0
a = []
for i in range(1,m+1):
  for j in l[i]:
    heappush(a,-j)
  if a:
    ans -= heappop(a)
print(ans)

Measured memory_bytes: 18516
import java.util.*;

public class Main{
    public static void main(String args[]){
        Scanner sn = new Scanner(System.in);
        int H = sn.nextInt();
        int W = sn.nextInt();
        String[][] S = new String[H][W];
        int N[][] = new int[H][W];
        int r0 = 0;
        int r1 = H-1;
        int c0 = 0;
        int c1 = W-1;
        int cnt = 0;

        for(int i=0; i<H; i++){
            String s = sn.next();
            for(int j=0; j<W; j++){
                S[i][j] = s.substring(j, j+1);
            }
        }

        if(S[0][0].equals("#")) N[0][0] = 1;
        else N[0][0] = 0;

        for(int i=0; i<H; i++){
            for(int j=0; j<W; j++){
                if(i == 0 && j == 0) continue;

                if(i == 0){
                    if(S[i][j].equals("#") && S[i][j-1].equals(".")){
                        N[i][j] = N[i][j-1] + 1;
                    }else{
                        N[i][j] = N[i][j-1];
                    }
                }else if(j == 0){
                    if(S[i][j].equals("#") && S[i-1][j].equals(".")){
                        N[i][j] = N[i-1][j] + 1;
                    }else{
                        N[i][j] = N[i-1][j];
                    }
                }else{
                    if(S[i][j].equals("#") && S[i-1][j].equals(".")){
                        if(S[i][j-1].equals(".")){
                            N[i][j] = Math.min(N[i-1][j]+1, N[i][j-1]+1);
                        }else{
                            N[i][j] = Math.min(N[i-1][j]+1, N[i][j-1]);
                        }
                    }else{
                        if(S[i][j].equals("#") && S[i][j-1].equals(".")){
                            N[i][j] = Math.min(N[i-1][j], N[i][j-1]+1);
                        }else{
                            N[i][j] = Math.min(N[i-1][j], N[i][j-1]);
                        }
                        
                    }
                }
            }
        }

        System.out.println(N[H-1][W-1]);
    }
}

Measured memory_bytes: 22228
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;

#define rep(i, n) for(int i=0;i<(int)n;i++)
#define rep2(i, s, n) for(int i=(s);i<(int)n;i++)
int INF=1e9+7;

int main() {
  int N;
  cin >> N;
  vector<int> a(N),b(N),c;
  rep(i,N) cin >> a[i];
  for(int i=N;i>0;i--) {
    int m=N/i, s=0;
    rep(j,m) s+=b[i*(j+1)-1];
    if(s%2!=a[i-1]) {
      b[i-1]=1;
      c.push_back(i);
    }
  }
  int ans=c.size();
  cout << ans << endl;
  rep(i,ans) cout << c[i] << ' ';
}

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

#define MAXN 50010
#define mod 998244353

char a[MAXN],b[MAXN];
int n,m,l,fac[MAXN],inv[MAXN],val[MAXN],res;

int qpow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)res=(long long)res*a%mod;
		a=(long long)a*a%mod;
		b>>=1; 
	}
	return res;
}

int c(int n,int m)
{
	return (long long)fac[n]*inv[m]%mod*inv[n-m]%mod;
}

int calc(int n,int m,int k)
{
	return (long long)c(m,k)*fac[k]%mod*fac[m-k]%mod*fac[m-k]%mod*c(n+m,m-k)%mod;
}

int main()
{
	scanf("%s%s",a+1,b+1);
	l=strlen(a+1);
	for(int i=1;i<=l;++i)
	{
		n+=a[i]=='1'&&b[i]=='0';
		m+=a[i]=='1'&&b[i]=='1';
	}
	fac[0]=1;
	for(int i=1;i<=50000;++i)fac[i]=(long long)fac[i-1]*i%mod;
	inv[50000]=qpow(fac[50000],mod-2);
	for(int i=49999;i>=0;--i)inv[i]=(long long)inv[i+1]*(i+1)%mod;
	for(int i=0;i<=n;++i)val[i]=(long long)c(n,i)*qpow(i,n)%mod;
	for(int k=0;k<=m;++k)
	{
		long long tmp=0;
		for(int i=0;i<=n;++i)
		{
			if(n-i&1)tmp-=val[i];else tmp+=val[i];
			tmp%=mod;
		}
		tmp+=mod;
		tmp%=mod;
		res=(res+(long long)fac[n]*tmp%mod*calc(n,m,k)%mod)%mod;
		for(int i=0;i<=n;++i)
		{
			val[i]=(long long)val[i]*i%mod;
		}
	}
	printf("%d\n",res);
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>
 
template <class T>
std::vector<T> ToFixedArray(std::istream& is, int n) {
	std::vector<T> ret(n);
	auto* dst = ret.data();
	while(n-- > 0)
		is >> *dst++;
	return ret;
}
 
#define _For(idx, from, to, inc, cmp) \
	for(auto idx=(from) ; idx cmp (to) ; inc idx)
#define ForLE(idx, from, to) \
	_For(idx, from, to, ++, <=)
#define ForGE(idx, from, to) \
	_For(idx, from, to, --, >=)
#define ForLT(idx, from, to) \
	_For(idx, from, to, ++, <)
#define ForGT(idx, from, to) \
	_For(idx, from, to, --, >)
#define For(idx, from, to) \
	_For(idx, from, to, ++, <)
 
void DisableIOSync() {
	std::cin.tie(0);
	std::cout.tie(0);
	std::ios::sync_with_stdio(false);
}
struct Link {
	int	toId,
		cost;
};
struct City {
	using LinkV = std::vector<Link>;
	LinkV	link;
};
using Dist_t = uint64_t;
constexpr auto DistMax = std::numeric_limits<Dist_t>::max()/2;
using CityV = std::vector<City>;
using DistV = std::vector<Dist_t>;
DistV BellmanFord(CityV& city, const int start) {
	const int Len = city.size();
	DistV ret(Len, DistMax);
	ret[start] = 0;
	For(i, 0, Len) {
		For(from, 0, Len) {
			auto& c = city[from];
			for(auto& lk : c.link) {
				if(ret[lk.toId] > ret[from] + lk.cost)
				{
					ret[lk.toId] = ret[from] + lk.cost;
				}
			}
		}
	}
	return ret;
}
struct FromTo {
	int	from, to;
	FromTo(const int f, const int t):
		from(f),
		to(t)
	{
		if(from > to)
			std::swap(from, to);
	}
	bool operator == (const FromTo& f) const {
		return from == f.from &&
				to == f.to;
	}
};
namespace std {
	template <>
	struct hash<FromTo> {
		std::size_t operator() (const FromTo& f) const {
			return (f.from << 16) | f.to;
		}
	};
}
#include <unordered_map>
int main() {
	DisableIOSync();

	using std::cin;
	using namespace std;
	int NCity, NLink, NDest;
	cin >> NCity >> NLink >> NDest;

	auto dest = ToFixedArray<int>(std::cin, NDest);
	for(auto& d : dest)
		--d;

	CityV city(NCity);
	For(i, 0, NLink) {
		int id0, id1, cost;
		cin >> id0 >> id1 >> cost;
		--id0;
		--id1;
		city[id0].link.emplace_back(Link{id1, cost});
		city[id1].link.emplace_back(Link{id0, cost});
	}

	std::unordered_map<FromTo, Dist_t> cache;
	const auto getDist = [&cache, &city](const FromTo& f){
		const auto itr = cache.find(f);
		if(itr != cache.end())
			return itr->second;
		return cache[f] = BellmanFord(city, f.from)[f.to];
	};
	Dist_t res = DistMax;
	std::sort(dest.begin(), dest.end());
	do {
		Dist_t sum = 0;
		For(i, 1, NDest) {
			sum += getDist({dest[i-1], dest[i]});
		}
		res = std::min(res, sum);
	} while(std::next_permutation(dest.begin(), dest.end()));
	std::cout << res << std::endl;
	return 0;
}


Measured memory_bytes: 896
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define all(a) (a).begin(),(a).end()
#define X first
#define Y second
#define inf 2e9+5
using namespace std;
void solve()
{
  int n; cin>>n; int a[n];
  for(int i=0;i<n;i++)cin>>a[i];
  int trn=1; int dp[n][n];
  for(int i=0;i<n;i++)
  {
      trn=1-trn;
    for(int j=0;j+i<n;j++)
  {
      if(!i){dp[j][j]=a[j]; continue;}
      if(!trn)
          dp[j][j+i]=max(dp[j+1][j+i]+a[j],dp[j][j+i-1]+a[j+i]);
      else
        dp[j][j+i]=min(dp[j+1][j+i]-a[j],dp[j][j+i-1]-a[j+i]);
  }
  }
  if(!trn)cout<<dp[0][n-1];
  else cout<<-dp[0][n-1];
  return;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t; t=1;
    while(t--)solve();
    return 0;
}


Measured memory_bytes: 49808
from collections import defaultdict
from itertools import product

H, W = map(int, input().split())
c = [[int(x) for x in input().split()] for _ in range(10)]
A = defaultdict(int)
for _ in range(H):
    for x in input().split():
        x = int(x)
        if x != -1 and x != 1:
            A[x] += 1

for _, i, j, k in product(range(10), range(10), range(10), range(10)):
    if i == 1 or k == 1:
        continue
    c[i][j] = min(c[i][j], c[i][k] + c[k][j])

ans = 0
for k, v in A.items():
    ans += c[k][1] * v
print(ans)

Measured memory_bytes: 3572
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
using namespace std;
#define N 998244353

int main() {
    int n;
    cin >> n;
    long long int v[n];
    long long int max_v = 0;
    long long int array[n];
    for(int i = 0; i < n; i++) array[i] = 0;
    for(int i = 0; i < n; i++) {
        cin >> v[i];
        array[v[i]]++;
        max_v = max(max_v, v[i]);
    }

    long long int ans = 1;
    
    for(int i = 1; i <= max_v; i++) {
        //long long int tmp = array[i];
        //long long int tmp2 = array[i-1];
        for(int j = 0; j < array[i]; j++) {
            ans = ans * array[i-1] % N;
        }
    
    }

    cout << ((v[0] == 0 && array[0] == 1) ? ans : 0) << endl;
    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair <int, int>
#define pll pair <ll, ll>
#define pci pair <char, int>
#define pld pair <ld, ld>
#define ppld pair <pld, pld>
#define ppll pair <pll, pll>
#define pldl pair <ld, ll>
#define vll vector <ll>
#define vvll vector <vll>
#define vpll vector <pll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mll map <ll, ll>
#define fastmap gp_hash_table
#define cd complex <double>
#define vcd vector <cd>
#define PI 3.14159265358979
#pragma 03
using namespace std;
using namespace __gnu_pbds;
// chctxdy
int main(){
	string s; cin >> s;
	ll cnta = 0, cntb = 0;
	for (ll i = 0; i<s.length(); i++){
		if (s[i] == 'A') cnta++; 
		else cntb++;
	}
	if (cnta > 0 && cntb > 0) cout << "Yes\n";
	else cout << "No\n";
}

Measured memory_bytes: 256
from functools import reduce


def gcd(v1, v2):
    v3 = v1 % v2
    if v3 == 0:
        return v2
    return gcd(v2, v3)


def main():
    N = int(input())
    A = [int(v) for v in input().split()]

    max_gcd = max(reduce(gcd, A[1:]), reduce(gcd, A[:N-1]))

    left = [1] * N
    left[0] = A[0]
    for i in range(1, N):
        left[i] = gcd(A[i], left[i - 1])

    right = [1] * N
    right[N-1] = A[N-1]
    for i in range(N - 2, -1, - 1):
        right[i] = gcd(A[i], right[i + 1])

    # print(left)
    # print(right)

    max_gcd = max(right[1], left[N-2])
    for i in range(1, N - 1):
        max_gcd = max(max_gcd, gcd(left[i - 1], right[i + 1]))

    print(max_gcd)


if __name__ == "__main__":
    main()


Measured memory_bytes: 14648