akhauriyash/Code-Regression huggingface dataset:
class ModInt(x: Long) {

    companion object {
        const val MOD = 1e9.toLong() + 7
    }

    val x = (x % MOD + MOD) % MOD

    operator fun plus(other: ModInt): ModInt {
        return ModInt(x + other.x)
    }

    operator fun plus(other: Long): ModInt {
        return this + ModInt(other)
    }

    operator fun minus(other: ModInt): ModInt {
        return ModInt(x - other.x)
    }

    operator fun minus(other: Long): ModInt {
        return this - ModInt(other)
    }

    operator fun times(other: ModInt): ModInt {
        return ModInt(x * other.x)
    }

    operator fun times(other: Long): ModInt {
        return this * ModInt(other)
    }

    operator fun div(other: ModInt): ModInt {
        return this * other.inv()
    }

    fun pow(exp: Long): ModInt {
        if (exp == 0L) return ModInt(1L)
        var a = pow(exp shr 1)
        a *= a
        if (exp and 1L == 0L) return a
        return this * a
    }

    fun pow(exp: Int): ModInt {
        return pow(exp.toLong())
    }

    fun inv(): ModInt {
        return this.pow(MOD - 2)
    }

    override fun equals(other: Any?): Boolean {
        if (this === other) return true
        if (javaClass != other?.javaClass) return false

        other as ModInt

        if (x != other.x) return false

        return true
    }

    override fun hashCode(): Int {
        return x.hashCode()
    }

    override fun toString(): String {
        return "$x"
    }

}

fun gcd(a: Long, b: Long): Long {
    return if (b == 0L) a else gcd(b, a % b)
}

fun main() {
    val n = readLine()!!.toInt()
    val cnt = mutableMapOf<Pair<Long, Long>, Pair<Int, Int>>()
    repeat(n) {
        var (a, b) = readLine()!!.split(' ').map { it.toLong() }
        when {
            a == 0L && b == 0L -> {
                cnt[a to b] = (cnt[a to b] ?: 0 to 0).let { (a, b) -> a + 1 to b }
            }
            a == 0L -> {
                b = 1
                cnt[a to b] = (cnt[a to b] ?: 0 to 0).let { (a, b) -> a + 1 to b }
            }
            b == 0L -> {
                a = 0L
                b = 1L
                cnt[a to b] = (cnt[a to b] ?: 0 to 0).let { (a, b) -> a to b + 1 }
            }
            else -> {
                val g = gcd(a, b)
                a /= g
                b /= g
                if (a < 0) {
                    a = -a
                    b = -b
                }
                if (b >= 0) {
                    cnt[a to b] = (cnt[a to b] ?: 0 to 0).let { (a, b) -> a + 1 to b }
                } else {
                    cnt[-b to a] = (cnt[-b to a] ?: 0 to 0).let { (a, b) -> a to b + 1 }
                }
            }
        }
    }

    var ans = ModInt(1L)
    val base = ModInt(2)

    for (key in cnt.keys.filter { it.first != 0L || it.second != 0L }) {
        val (c1, c2) = cnt[key]!!
        ans *= base.pow(c1) - 1 + base.pow(c2) - 1 + 1
    }
    ans -= 1
    ans += (cnt[0L to 0L]?.first ?: 0).toLong()

    println(ans)
}


Measured memory_bytes: 97752
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=200005;
int N,A[MAXN],B[MAXN];
long long Ans;
int Check(){
	for(int i=1;i<=N;i++)
		if(B[i]!=A[i])return 0;
	return 1;
}
int Get(int x){
	if(x==0)return N;
	if(x==N+1)return 1;
	return x;
}
int main(){
	//freopen("txt.in","r",stdin);
	//freopen("hopeless.in","r",stdin);
	//freopen("hopeless.out","w",stdout);
	scanf("%d",&N);
	for(int i=1;i<=N;i++)scanf("%d",&A[i]);
	for(int i=1;i<=N;i++)scanf("%d",&B[i]);
	while(!Check()){
		int Ok=0;
		for(int i=1;i<=N;i++)
			if(B[i]-B[Get(i-1)]-B[Get(i+1)]>=A[i]){
				int t1=B[i]-A[i],t2=B[Get(i-1)]+B[Get(i+1)];
				B[i]=t1%t2+A[i];Ans+=t1/t2,Ok=1;
			}
		if(!Ok){
			printf("-1\n");
			return 0;
		}
	}
	printf("%lld\n",Ans);
}
/*
5
5 6 5 2 1
9817 1108 6890 4343 8704

5
1 2 5 6 5
8704 4343 6890 1108 9817

5
1 1 1 1 1
1 1000000001 1 1000000001 1
*/

Measured memory_bytes: 1664
N,x = map(int,input().split())
A = list(map(int,input().split()))
cnt = 0
for i in range(1,N):
    if A[i]+A[i-1]>x:
        d = A[i]+A[i-1]-x
        if A[i]>=d:
            A[i] -= d
            cnt += d
        else:
            A[i]=0
            cnt += A[i]
            d -= A[i]
            A[i-1] -= d
            cnt += d
print(cnt)

Measured memory_bytes: 84948
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define DEBUG true
#ifdef ONLINE_JUDGE
#undef DEBUG
#define DEBUG false
#endif 

using namespace std;

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

int n;
vector <int> v;
int ans;

int main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);
	cin >> n;
	v.resize(n);

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

	sort(all(v));

	for (int i = 0; i < n; ++i)
	{
		for (int j = i+1; j < n; ++j)
		{
			int minval = v[j] - v[i];
			int maxval = v[j] + v[i] - 1;

			auto p1 = upper_bound(all(v), minval); // first > minval
			auto p2 = upper_bound(all(v), maxval); // first non working index

			int i1 = max(int(p1 - v.begin()), j+1);
			int i2 = p2 - v.begin();

			// TRACE2(i1,i2);
			ans += (i2-i1);
		}
	}

	cout << ans << endl;
}

Measured memory_bytes: 384
import java.util.*;

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

        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();

        if ( ((c > a) && (c < b)) || ((c < a) && (c > b)) )  {
            System.out.println("Yes");
        }
        else System.out.println("No");

    }
}


Measured memory_bytes: 22868
#ifdef DEBUG

#else

#    pragma GCC optimize("O3,no-stack-protector")
#    pragma GCC optimize("unroll-loops")

#    if __cplusplus < 201703L
#        pragma GCC target("avx")
#    else
#        pragma GCC target("avx2")
#    endif

#endif
// 実数の場合
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define dump(x) cout << x << endl
typedef int64_t Int;
typedef long double Ld;

using namespace std;
using Graph = vector<vector<Int>>;

const double pi = M_PI;
const Int MOD = 1000000007;

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

    string s;
    cin >> s;

    int a = (s[0] - '0') * 10 + (s[1] - '0');
    int b = (s[2] - '0') * 10 + (s[3] - '0');

    if ((a < 1 || 12 < a) && (1 <= b && b <= 12)) {
        cout << "YYMM" << endl;
    } else if ((1 <= a && a <= 12) && (b < 1 || 12 < b)) {
        cout << "MMYY" << endl;
    } else if ((b < 1 || 12 < b) && (a < 1 || 12 < a)) {
        cout << "NA" << endl;
    } else {
        cout << "AMBIGUOUS" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using vl=vector<long long>;
using pii=pair<int,int>;
using pll=pair<long long,long long>;
#define ITR(i,c) for(auto i=begin(c);i!=end(c);++i)
#define FORE(x,c) for(auto &x:c)
#define FOR(i,a,n) for(int i=a,i##_len=(int)n;i<i##_len;++i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for(int i=((int)(n)-1);i>=0;--i)
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)   // c++14
#define SZ(c) ((int)c.size())
#define EXIST(c,x) (c.find(x)!=end(c))
#define dump(...)
const int DX[9]={0,1,0,-1,1,1,-1,-1,0}, DY[9]={-1,0,1,0,-1,1,1,-1,0};
const int INF=1001001001; const long long INFLL=1001001001001001001ll;
template<class T> ostream& operator << (ostream &os, const vector<T> &v) {
    ITR(i,v) os << *i << (i==end(v)-1 ? "" : " "); return os; }
template<class T> istream& operator >> (istream &is, vector<T> &v) {
    ITR(i,v) is >> * i; return is; }
template<class T> istream& operator >> (istream &is, pair<T,T> &p) {
        is >> p.first >> p.second; return is; }
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
//------------------------------------------------------------------------------
struct before_main_function {
    before_main_function() {
    #ifdef int
        cerr<<"\x1b[7m"<<"'int' is defined as 'long long' !!!!"<<"\x1b[m"<<endl;
    #endif
        cin.tie(0);ios::sync_with_stdio(false);
        cout<<setprecision(12)<<fixed;
    }
} before_main_function;
//------------------------------------------------------------------------------

signed main() {
    string s;
    cin>>s;
    s[5]=' ';
    s[13]=' ';
    cout<<s<<endl;
    return 0;
}


Measured memory_bytes: 256
/*..............IN THE NAME OF ALLAH.............*/
/**
*     => Md. Sajjat Hosen
*     => Department of Computer Science and Engineering
*     => Bangabandhu Sheikh Mujibur Rahman Science and Technology University
**/

/*..................! TRY ONCE MORE !..................*/

/*...Part - 01...*/

#include <bits/stdc++.h>
using namespace std ;

/*...Part - 02...*/

typedef long long               ll ;
typedef long double             ld ;
typedef unsigned long long      ull ;
typedef pair<int,int>           pii ;
typedef pair<ll,ll>             pll ;
typedef vector<int>             vi ;
typedef vector<ll>              vll ;
typedef vector<vector<int>>     vvi ;

int Int(){int x ; scanf("%d",&x) ; return x ;}
ll Long(){ll x ; scanf("%lld",&x) ; return x ;}
float Float(){float x ; scanf("%f",&x) ; return x ;}
double Double(){double x ; scanf("%lf",&x); return x;}

/*...Part - 03...*/
/*....Debugger....*/

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {cout << endl ;}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << ' ' ;
    err(++it, args...);
}

/*...Part - 04...*/
/*...Needed to change according to problem requirements...*/

const int N          = (int)2e5 + 5 ;
const int maxN       = (int)1e6 + 6 ;
const ll  Mod        = (ll)1e9 + 7 ;
const int inf        = (int)2e9 ;
const ll  Inf        = (ll)1e18 ;

/*..........................................................*/
/*...Part - 05...*/

#define     debug(x)    cerr << #x << " = " << x << '\n' ;
#define     rep(i,b,e)  for(__typeof(e) i = (b) ; i != (e + 1) - 2 * ((b) > (e))  ; i += 1 - 2 * ((b) > (e)))
#define     Int         Int()
#define     Long        Long()
#define     Float       Float()
#define     Double      Double()
#define     all(x)      x.begin() , x.end()
#define     sz(x)       (int)x.size()
#define     ff          first
#define     ss          second
#define     pb          push_back
#define     eb          emplace_back
#define     mem(a)      memset(a , 0 ,sizeof a)
#define     memn(a)     memset(a , -1 ,sizeof a)

/*...Part - 06...*/
/*...... ! Code start from here ! ......*/

ll a, b, ans , n, x, y;

int main(){
    //freopen("input.txt","r",stdin);
    int test = 1 , tc = 0 ;
    while(test--){
        n = Long;
        a = Long;
        b = Long;
        if(n % (a + b) == 0){
            x = n / (a + b);
            ans = x*a;
        }
        else{
            x = n / (a + b);
            ans = x*a;
            n -= x*(a + b);
            ans += min(n, a);
        }
        printf("%lld\n", ans);
    }
    return 0 ;
}

/*...Always look at the part - 04...*/
/*...............END................*/

Measured memory_bytes: 256
/**
 *    author:  tourist
 *    created: 11.05.2020 13:45:18       
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int x;
  cin >> x;
  int y = 1;
  while (y * y * y * y <= x) {
    ++y;
  }
  for (long long a = -y; a <= y; a++) {
    for (long long b = -y; b <= y; b++) {
      if (a * a * a * a * a - b * b * b * b * b == x) {
        cout << a << " " << b << '\n';
        return 0;
      }
    }
  }
  return 0;
}


Measured memory_bytes: 3592
def rec x, y
  z = [x, y].max % [x, y].min
  return [x, y].min if z == 0
  rec z, [x, y].min
end

while line = gets do
  a, b = line.split.map(&:to_i)
  ans1 = rec a, b
  ans2 = ans1 * (a/ans1) * (b/ans1)
  printf("%d %d\n", ans1, ans2)
end

Measured memory_bytes: 2372
#include<stdio.h>
int main(){
    int r, c, n[101][101]={0};
    scanf("%d %d",&r,&c);
    for (int i=0;i<r;i++){
        for (int j=0;j<c;j++){
            scanf("%d",&n[i][j]);
        }
    }
    for (int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            n[i][c]=n[i][c]+n[i][j];
            n[r][j]=n[r][j]+n[i][j];
        }
    }
    for (int i=0;i<r;i++){
        n[r][c]=n[r][c]+n[i][c];
    }
    for(int i=0;i<r+1;i++){
        for(int j=0;j<c+1;j++){
            if (j==0){
                printf("%d",n[i][j]);
            }else{
                printf(" %d",n[i][j]);
            }
        }
        printf("\n");
    }
}


Measured memory_bytes: 2040
#include <iostream>
int main(){
	int x,y,a,b,i;
	for(i=0;i<10000;i++)
  {
    std::cin >> x >> y;
	if(x==0 && y==0)break;
	if(x>y){
		a=y;
		b=x;
	}else{
		a=x;
		b=y;
	}
    std::cout << a << " " << b <<std::endl;
  }
	return 0;
}

Measured memory_bytes: 1160
///Bismillahir Rahmanir Rahim
#include<bits/stdc++.h>

#define                           int                         long long
#define                           fi                          first
#define                           si                          second
#define                           mp                          make_pair
#define                           pb                          push_back
#define                           pi                          pair<int,int>
#define                           f(i,l,r)                    for(int i=l;i<=r;i++)
#define                           rf(i,r,l)                   for(int i=r;i>=l;i--)
#define                           done(i)                     cout<<"done = "<<i<<endl;
#define                           fast                        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);




using namespace std;

const int inf=1e18;
const int mod=1e9+7;
const int M=100009;
inline int bigmod(int B,int P){int R=1;while(P>0){if(P&1){R=(R*B)%mod;}P>>=1;B=(B*B)%mod;}return R;}


 main()

{
    fast
    int n,k;
    cin>>n>>k;
    int cnt[n+4]={0};
    f(i,1,k)
    {
        int d;
        cin>>d;
        f(j,1,d)
        {
            int x;
            cin>>x;
            cnt[x]++;
        }
    }
    int ses=0;
    f(i,1,n)
    {
        if(cnt[i]==0)ses++;
    }
     cout<<ses<<endl;

















    return 0;

}













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

using namespace std;

int n , x;
int f[1000];
int main (){
    cin >> x >> n;
    for(int i = 0; i < n; ++i){
        int a;
        cin >> a; a+=105;
        f[a]++;
    }
    if(n == 0) {cout << x << endl; return 0;}
    int A = -1 , B = -1;
    x+=105;
    for(int i = 0; i <= 210; ++i){
        if(!f[i]){
            if(i <= x) A = i;
            else {B = i; break;}
        }
    }
    if(A == -1) cout << B -105<< endl;
    else if(B == -1) cout << A -105 << endl;
    else {
        if(x - A <= B - x) cout << A-105 << endl;
        else cout << B-105;
    }

}


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

int abs(int x) {
    return max(x, -x);
}

int main() {
  int N;
  cin >> N;
  vector<vector<int>> v(N, vector<int> (3));
  for (int i = 0; i < N; i++) {
    int t, x, y;
    cin >> t >> x >> y;
    v.at(i).at(0) = t;
    v.at(i).at(1) = x;
    v.at(i).at(2) = y;
  }
  v.push_back({0, 0, 0});
  sort(v.begin(), v.end());
  for (int i = 0; i < N; i++) {
    int dl = abs(v.at(i).at(1)-v.at(i+1).at(1)) + abs(v.at(i).at(2)-v.at(i+1).at(2));
    int dt = v.at(i+1).at(0) - v.at(i).at(0);
    if (dt % 2 != dl % 2) {
      cout << "No" << endl;
      break;
    }
    if (dt < dl) {
      cout << "No" << endl;
      break;
    }
    if (i == N-1) cout << "Yes" << endl;
  }
}

Measured memory_bytes: 9856
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    String s = sc.next();
    int dpw[] = new int[n];
    int dp[] = new int[n];

    if (s.charAt(0) == 'W') {
      dpw[0] = 1;
    } else {
      dpw[0] = 0;
    }
    dp[0] = 0;
    for (int i = 1; i < n; i++) {
      if (s.charAt(i) == 'W') {
        dpw[i] = dpw[i - 1] + 1;
        dp[i] = dp[i - 1];
      } else {
        dpw[i] = dpw[i - 1];
        dp[i] = dp[i - 1] + 1;
      }
      if (dpw[i - 1] < dp[i]) {
        dp[i] = dpw[i - 1];
      }
    }
    System.out.println(dp[n - 1]);
  }
}

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

ll h[200010],n,tt;
char s[200010];
bool bo[200010];

inline int rd()
{
	int x=0;char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar());
	for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x;
}

int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	tt=0;
	for (int i=1;i<=n;i++) if (s[i]=='A')
	{
		tt++;int id=0;
		for (int j=i+1;j<=n-1;j+=2) if (s[j]=='B'&&s[j+1]=='C') h[tt]++;else { id=j;break; }
		if (id&&s[id]=='A') bo[tt]=true;
	}
	for (int i=tt-1;i>0;i--) if (bo[i]) h[i]+=h[i+1];
	ll ans=0;
	for (int i=1;i<=tt;i++) ans+=h[i];
	printf("%lld\n",ans);
	return 0;
}

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

int main(){

  int w, h, n;
  int x, y, xx, yy;
  int cnt = 0;

  cin >> w >> h >> n;
  cin >> x >> y;

  while(--n){
    cin >> xx >> yy;

    while(x != xx || y != yy){
      if(xx > x) x++;
      else if(yy < y) y--;

      if(yy > y) y++;
      else if(xx < x) x--;

      cnt++;
    }
    
  }

  cout << cnt << endl;

}

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

using namespace std;



int main()
{
    std::ios::sync_with_stdio(false);
    /*#ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input.txt", "r", stdin);
    // for writing output to output.txt
    freopen("output.txt", "w", stdout);
    #endif*/
    int n;
    cin >> n;
    vector<vector<int> > arr(n,vector<int>(3));
    for(int i = 0;i < n;i++)
        cin >> arr[i][0] >> arr[i][1] >> arr[i][2];
    for(int i = 1;i < n;i++)
    {
        for(int j = 0;j < 3;j++)
        {
            if(j == 0)
            {
                arr[i][j] += max(arr[i-1][1],arr[i-1][2]);
            }
            else if(j == 1)
            {
                arr[i][j] += max(arr[i-1][0],arr[i-1][2]);
            }
            else
            {
                arr[i][j] += max(arr[i-1][1],arr[i-1][0]);
            }
        }
    }
    cout << max(arr[n-1][0],max(arr[n-1][1],arr[n-1][2])) << endl;
    return 0;
}

Measured memory_bytes: 5760
//#include<bits\stdc++.h>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<string>
#include<ctime>
#include<cmath>
#include<cctype>
#include<cstdlib>
#include<queue>
#include<deque>
#include<stack>
#include<vector>
#include<algorithm>	
#include<utility>
#include<bitset>
#include<set>
#include<map>
#define ll long long
#define db double
#define ld long double
#define put(x) printf("%d\n",x)
#define min(x,y) ((x)>(y)?(y):(x))
#define max(x,y) ((x)>(y)?(x):(y))
#define EPS 1e-8
#define mod 1000000007
#define INF 1000000000
using namespace std;
char *fs,*ft,buf[1<<15];
inline char getc()
{
	return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline int read()
{
    int x=0,f=1;char ch=getc();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}
    return x*f;
}
const int MAXN=1000010<<1;
int n,m,w;
int ans;
int main()
{
	//freopen("1.in","r",stdin);
	n=read();m=read();w=read();
	if(n>m)ans=w%n==0?w/n:w/n+1;
	else ans=w%m==0?w/m:w/m+1;
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }
#define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; }
#define dump(x) cerr<<#x<<": "<<x<<endl;
#define bit(k) (1LL<<(k))
#define Yes "Yes"
#define No "No"
#define YES "YES"
#define NO "NO"
typedef long long ll;

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

const int INF = (ll)1e9;
const ll INFLL = (ll)1e17;
const ll MOD = (ll)1e9+7;
const double PI = acos(-1.0);
/*
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const string dir = "DRUL";
*/
template<typename T>
vector<T> cumulative_sum(vector<T> &v) {
    vector<T> sum(v.size() + 1);
    for(int i = 0; i < (int)v.size(); ++i){
        sum[i+1] = sum[i] + v[i];
    }
    return sum;
}
/*使うとき
vector<int> a(N);
auto cum = cumlative_sum(a)
とするとvector<int> cumが生成される

i番目までの仕切りの和
cum[i]: [0,i)の和（半開区間）

要素i~jの和が欲しい時
j+1 ~ i番目の仕切りまで数えればよい
int sum = cum[j+1]-cum[i]
*/
int N;
//dp[l][r]: [l, r)の区間を作るための最小値
ll dp[432][432];
void debug(){
    rep(i,N){
        rep(j,N){
            if(dp[i][j] == INFLL)cerr<<-1<<" ";
            else cerr<<dp[i][j]<<" ";
        }
        cerr<<endl;
    }
    cerr<<endl;
}
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    cin >> N;
    vector<ll> a(N);
    rep(i,N)cin>>a[i];
    auto cum = cumulative_sum(a);
    auto summ = [&](int l, int r){
        return cum[r] - cum[l];
    };

    rep(i, N+1)rep(j, N+1){
        dp[i][j] = INFLL;
    }
    //長さ0, 1の場合の初期化
    rep(i,N+1){
        dp[i][i] = 0;
        dp[i][i+1] = 0;
    }
    //長さを全探索
    for(int len = 2; len <= N; len++){
        for(int l = 0; l < N; l++){
            int r = l + len;
            if(r > N)continue;
            for(int k = l;k <= r;k++){
                chmin(dp[l][r], dp[l][k] + dp[k][r] + summ(l,r));            
            }
        }
    }
    cout << dp[0][N] << endl;
}

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    string a, b;
    cin >> a >> b;
    
    string ans = "";
    for(int i = 0; i < n; i++){
        ans += a[i];
        ans += b[i];
    }
    cout << ans;
}

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

#define int long long

int m, n;
int w[200010];
int t[200010];
int c[20];
int d[20];

int dp[(1 << 15)];

int search(int idx, int l){
    int st = l;
    int r = m+1;

    while(r-l > 1){
        int mid = (r+l)/2;
        int ww = w[mid]-w[st];
        int tt = t[mid]-t[st];
        if(ww <= c[idx] && tt <= d[idx]){
            l = mid;
        }else{
            r = mid;
        }
    }

    return l;
}

int solve(){

    dp[0] = 0;

    for(int i = 0;i < (1 << n);i++){
        dp[i] = -1;
        for(int j = 0;j < n;j++){
            if((i & (1 << j)) != 0){
                dp[i] = max(dp[i], search(j, dp[i^(1 << j)]));
            }
        }
    }

    return dp[(1 << n)-1];
}

signed main(){
    cin >> m >> n;
    for(int i = 0;i < m;i++){
        cin >> w[i+1] >> t[i+1];
        w[i+1] += w[i];
        t[i+1] += t[i];
    }

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

    cout << solve() << endl;

    return 0;
}



Measured memory_bytes: 6444
#include <bits/stdc++.h>
using namespace std;
 
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define f first
#define s second
#define resz resize
 
#define sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
 
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define F0R(i, a) for (ll i = 0; i < (a); i++)
#define FORR(i, a, b) for (ll i = a; i >= (b); i--)
#define F0RR(i, a) for (ll i = a; i >= 0; i--)
#define trav(a, x) for (auto& a : x)

using ll = long long;
using vi = vector<ll>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vd = vector<double>;
using vs = vector<string>;
 
using pii = pair<ll, ll>;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
 
using vpii = vector<pii>;
using vvpii = vector<vpii>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
using vpdd = vector<pdd>;
using vvpdd = vector<vpdd>;
 
ll gcd(ll a,ll b)
{
    if(b==0)return a;
    else return gcd(b,a%b);
}
ll po(ll a,ll b)
{
    ll ans = 1;
    while(b--)
        ans*=a;
    return ans;
}
ll pom(ll a,ll b,ll mod)
{
    if(b==0)return 1;
    ll k = pom(a,b/2,mod);
    if(b%2==0)return (k*k)%mod;
    else return ((k*k)*mod*a)%mod;
}
 
ll sqdist(ll a,ll b,ll c,ll d)
{
    return (a-c)*(a-c)+(b-d)*(b-d);
}



int arr[10];
int a[10],b[10];


int cha(int n)
{
    FOR(i,0,n)
    {
        //cout<<"T"<<arr[i]<<' '<<a[i]<<endl;
        if(arr[i]!=a[i])return 0;
    }
    return 1;
}
int chb(int n)
{
    FOR(i,0,n)
    {
        if(arr[i]!=b[i])return 0;
    }
    return 1;
}
void solve()
{
int n;
cin>>n;
FOR(i,0,n)arr[i]=i+1;
FOR(i,0,n)cin>>a[i];
FOR(i,0,n)cin>>b[i];
int p = 1;
int c=0;
while(1)
{
    //if(c==100000)break;
    c++;
    if(cha(n))
        break;
    p++;
    next_permutation(arr,arr+n);
    // FOR(i,0,n)cout<<arr[i]<<' ';cout<<endl;
    // FOR(i,0,n)cout<<a[i]<<' ';cout<<endl;
}
c=0;
sort(arr,arr+n);
int q = 1;
while(1)
{    //if(c==100000)break;
    c++;
    if(chb(n))
        break;
    q++;
    next_permutation(arr,arr+n);
}
      cout<<abs(p-q)<<endl;                                                                                     
}

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

    // #ifndef ONLINE_JUDGE
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    // #endif
    // ll t;
    //cout<<"Y"<<endl;
    //cin>>t;
    //while(t--)
        solve();
}

Measured memory_bytes: 256
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <chrono>
#include <random>
#include <tuple>
#include <utility>
#include <fstream>

const long INF = (1l << 30);
const long LINF = (1l << 60);

typedef std::pair<long, std::vector<long> > P;
typedef std::pair<long, std::pair<long, std::vector<long> > > PP;

long n;
long d[50];



int main(){
	scanf("%ld", &n);
	for(int i = 0; i < n; i++){
		scanf("%ld", d+i);
	}
	std::priority_queue<PP> que;
	std::vector<long> v;
	v.push_back(0);
	que.push(PP(LINF, P(1l, v)));
	
	while(true){
		
		/*
		printf("que.size() = %ld\n", que.size());
		std::priority_queue<PP> que2;
		while(!que.empty()){
			PP out = que.top();
			que.pop();
			printf("  (%ld, (%ld, (", out.first, out.second.first);
			for(int i = 0; i < out.second.first; i++){
				printf("%ld ", out.second.second.at(i));
			}
			printf(")))\n");
			que2.push(out);
		}
		que.swap(que2);
		//*/
		
		PP vis = que.top();
		que.pop();
		long length = vis.second.first;
		
		/*
		printf("  (%ld, (%ld, (", vis.first, length);
		for(int i = 0; i < length; i++){
			printf("%ld ", vis.second.second.at(i));
		}
		printf(")))\n");
		//*/
		
		if(length == n+1){
			printf("%ld\n", vis.first);
			return 0;
		}
		
		//printf("    positive part\n");
		long posRes = vis.first;
		std::vector<long> posVec = vis.second.second;
		posVec.push_back(d[length-1]);
		for(int i = 0; i < length; i++){
			long d_i = std::abs(vis.second.second.at(i) - d[length-1]);
			posRes = std::min(posRes, std::min(d_i, 24-d_i));
		}
		que.push(PP(posRes, P(length+1, posVec)));
		
		//printf("    negative part\n");
		long negRes = vis.first;
		std::vector<long> negVec = vis.second.second;
		negVec.push_back(24-d[length-1]);
		for(int i = 0; i < length; i++){
			long d_i = std::abs(vis.second.second[i] - (24-d[length-1]));
			negRes = std::min(negRes, std::min(d_i, 24-d_i));
		}
		que.push(PP(negRes, P(length+1, negVec)));
	}
}


Measured memory_bytes: 6036
import java.util.*;

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

	while(sc.hasNext()){
	    String[] sentences = sc.nextLine().split(" ");
	    HashMap<String, Integer> map = new HashMap<String, Integer>();
	    
	    for(String sentence : sentences){
		if(map.get(sentence) == null){
		    map.put(sentence, 1);
		} else {
		    int count = (Integer)map.get(sentence);
		    map.put(sentence, count+1);
		}
	    }

	    Set key_list = map.keySet();
	    Iterator iter = key_list.iterator();
	    String str_max_length, str_freq;
	    str_max_length = str_freq = (String)iter.next();

	    while(iter.hasNext()){
		String str_key = (String)iter.next();

		str_max_length = compMaxLength(str_max_length, str_key);
		str_freq = compFreqSentence(str_freq, str_key, map);
	    }

	    System.out.println(str_freq+" "+str_max_length);
	}
    }

    private static String compMaxLength(String str1, String str2){
	return (str1.length() > str2.length())? str1 : str2;
    }

    private static String compFreqSentence(String str1, String str2, HashMap map){
	return ((Integer)map.get(str1) > (Integer)map.get(str2))? str1 : str2;
    }
}

Measured memory_bytes: 17144
/*By Mohan Abhyas V*/
#pragma GCC optimize ("-O3")
#include <bits/stdc++.h>  
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
typedef pair<double,double> pdd;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef vector<vector<int> > vv32;
typedef vector<vector<ll> > vv64;
typedef vector<vector<p64> > vvp64;
typedef vector<p64> vp64;
typedef vector<p32> vp32;
ll MOD = 998244353;
#define forn(i,e) for(ll i = 0; i < e; i++)
#define forsn(i,s,e) for(int i = s; i < e; i++)
#define rforn(i,s) for(ll i = s; i >= 0; i--)
#define rforsn(i,s,e) for(ll i = s; i >= e; i--)
#define ln "\n"
#define dbg(x) cout<<#x<<" = "<<x<<ln
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define INF 1e18
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())

ll mpow(ll a, ll b){
	if(b >= (MOD-1)) b %= (MOD-1);
	if(b==0) return 1;
	ll t1 = mpow(a,b/2);
	t1 *= t1;
	t1 %= MOD;
	if(b%2) t1 *= a;
	t1 %= MOD;
	return t1;
}

ll mpow(ll a, ll b, ll p){
	if(b==0) return 1;
	ll t1 = mpow(a,b/2,p);   t1 *= t1;
	t1 %= p;
	if(b%2) t1 *= a;
	t1 %= p;
	return t1;
}
ll modinverse(ll a, ll m){
	ll m0 = m; 
    ll y = 0, x = 1; 
    if (m == 1) return 0; 
    while (a > 1){
        ll q = a / m; 
        ll t = m; 
        m = a % m, a = t; 
        t = y; 
        y = x - q * y; 
        x = t; 
    }
    if (x < 0) x += m0; 
    return x; 
}
ll range(ll l, ll r){
	return l + rand()%(r-l+1);
}

p64 hashFn(v64 vc)
{
    ll p1 = 31, p2 = 97;
    ll m1 = 1e9+9, m2 = 998244353;
    ll hsv1 = 0, hsv2 = 0, p_pow1 = 1, p_pow2 = 1;
    forn(i, vc.size())
    {
        hsv1 = ((hsv1 + vc[i] + 1) * p_pow1) % m1;
        p_pow1 = (p_pow1 * p1) % m1;

        hsv2 = ((hsv2 + vc[i] + 1) * p_pow2) % m2;
        p_pow2 = (p_pow2 * p2) % m2;
    }
    return mp(hsv1, hsv2);
}
     
void solve(){
    string s;
    cin>>s;
    ll n = s.size();
    bool flg = 0, flg1 = 1, flg2 = 1, flg3 = 1;
    forn(i, n)
    {
        if(s[i] != s[n-1-i]) flg1 = 0;
    }
    forn(i, (n-1)/2)
    {
        if(s[i] != s[(n-1)/2-1-i]) flg2 = 0;
    }
    forn(i, (n-1)/2)
    {
        if(s[(n+3)/2-1+i] != s[(n+3)/2-1+(n-1)/2-1-i]) flg2 = 0;
    }
    if(flg1 && flg2 && flg3)
    {
        cout<<"Yes"<<ln;
    }
    else
    {
        cout<<"No"<<ln;
    }
}
 
int main()
{
	fast_cin();
    ll t=1;
    //cin>>t;
    forn(i,t) {
    	// cout << "Case #" << i+1 << ": ";
    	solve();
    }
    return 0;
}

/*
1) try dp
2) meet in the middle
3) correct complexity analysis
4) randomized algorithm
5) brute force

*/

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

using ll = long long;
using ii = pair<int, int>;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int n, x;
  int sum = 0;

  cin >> n >> x;

  int v, ans = 1;
  for (int i = 0; i < n; i++) {
    cin >> v;
    sum += v;

    if (sum <= x) ans++;
  }

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


Measured memory_bytes: 3644
#include <iostream>
#include <vector>
#include <cmath>
#include <map>
#include <algorithm>
using namespace std;
#define mp make_pair
typedef pair<double,double> pii;

const double agl = M_PI / 2;
vector<pii> temp1, temp2;	// temp1:そのまま temp2:逆

// 四捨五入
int roundOff( double x ){
	if( 0 <= x ) return (int)(x + 0.5);
	else				 return (int)(x - 0.5);
}

// 点を原点中心に(反時計周りに)回転
pii rotate( pii p ){
	double x = p.first, y = p.second;
	p.first = (x * cos(agl)) - (y * sin(agl));
	p.second = (x * sin(agl)) + (y * cos(agl));
	return mp(roundOff(p.first), roundOff(p.second));
}

// 90,180,270,360度に回転した折れ線について確かめる
bool isSame( vector<pii> l ){
	bool res = false;
	for( int r = 0; r < 4; r++ ){	// 90度づつ回転(clockwise)
		bool f1 = true, f2 = true;
		for( int i = 0; i < temp1.size(); i++ ){
			l[i] = rotate(l[i]);
			if( temp1[i] != l[i] ) f1 = false;
			if( temp2[i] != l[i] ) f2 = false;
		}
		if( f1 || f2 ) res = true;
	}
	return res;
}

int main(){
	int n;
	while( cin >> n, n ){
		vector<int> diff;
		for( int i = 0; i <= n; i++ ){
			int m;
			cin >> m;
			vector<pii> lines(m);
			double dx, dy;
			for( int j = 0; j < m; j++ ){
				int x, y;
				cin >> x >> y;
				if( j == 0 ){
					dx = x;
					dy = y;
				}
				lines[j] = mp(x-dx,y-dy);	// スタートを原点にするように平行移動
			}
			// 探したい折れ線を設定
			if( i == 0 ){
				temp1 = lines;
				reverse(lines.begin(), lines.end());
				temp2 = lines;
				dx = temp2[0].first;
				dy = temp2[0].second;
				for( int i = 0; i < m; i++ ){
					temp2[i] = mp(temp2[i].first-dx, temp2[i].second-dy);
				}
				continue;
			}
			if( temp1.size() != lines.size() ) continue;
			if( isSame(lines) ) diff.push_back(i);
		}

		// output
		for( int i = 0; i < diff.size(); i++ ) cout << diff[i] << endl;
		cout << "+++++" << endl;
	}
}

Measured memory_bytes: 1220
/*input
6 2 4
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#pragma GCC optimize("unroll-loops,no-stack-protector")
//order_of_key #of elements less than x
// find_by_order kth element
typedef long long int ll;
#define ld double
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
const ll maxn=3e3+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
const ll MOD=1e9+7;
const ld PI=3.14159265358979323846;
const ld eps=1e-9;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define MP make_pair
ll mult(ll a,ll b){
    ll res=0LL;
    while(b){
        if(b&1) res=(res+a)%MOD;
        a=(a+a)%MOD;
        b>>=1;
    }
    return res%MOD;
}
ll mypow(ll a,ll b){
    ll res=1LL;
    while(b){
        if(b&1) res=res*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    ll x,k,d;
    cin>>x>>k>>d;
    ll nd=(llabs(x)/d);
    x=llabs(x);
    if(nd>=k){
        if(x<0) x+=(k*d);
        else x-=(k*d);
    }
    else{
        k-=nd;
        x-=nd*d;
        if(k%2){
            x=llabs(x-d);
        }
    }
    cout<<x;
}



Measured memory_bytes: 3504
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define F first
#define S second
#define PB push_back
#define REP(i,a,b) for (int i = a ; i <= b ; i++)
#define REPI(i,a,b) for (int i = a ; i >= b ; i--)
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

const int OO = 1e9+7;
const int MOD = 1e9+7;
const int N = 20+7;

int b[N];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //freopen("teleport.in","r",stdin);
    //freopen("teleport.out","w",stdout);

    int n,m,c;
    cin >> n >> m >> c;
    REP(i,0,m-1) cin >> b[i];
    int ans = 0;
    REP(i,0,n-1)
    {
        int tmp = c;
        REP(i,0,m-1)
        {
            int a;
            cin >> a;
            tmp += a*b[i];
        }
        if (tmp > 0) ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iterator>
#pragma warning(disable:4996)
 
typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define MOD 1000000007
using namespace std;

ll aa[10005];

int main(int argc, char* argv[])
{
    char str[100005]={0};
    scanf("%s", str);
    
    long len=strlen(str);

    long i;
    if(len%2==1) {
        char tmp = str[(len-1)/2];
        long curr=(len-1)/2;
        for(i=1; i<=(len-1)/2; i++) {
            if(str[curr-i]!=tmp) break;
            if(str[curr+i]!=tmp) break;
        }
        printf("%ld\n", (len-1)/2+i);
    }
    else {
        char tmp = str[len/2];
        if(tmp!=str[len/2-1]) {
            printf("%ld\n", len/2);
            return 0;
        }
        long curr=len/2-1;
        for(i=1; i<=(len/2-1); i++) {
            if(str[curr-i]!=tmp) break;
            if(str[curr+1+i]!=tmp) break;
        }
        printf("%ld\n", len/2+i);
    }

    return 0;
}


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

using namespace std;

typedef long long ll;

int main()
{
	int N, D;
	cin >> D >> N;
	int tmp;
	if(D == 0) tmp = 1;
	else if(D == 1) tmp = 100;
	else tmp = 10000;

	if(N == 100) cout << (N + 1) * tmp << endl;
	else cout << N * tmp << endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <functional>

using namespace std;

int main()
{
	string buffer;

	while ( cin >> buffer )
	{
		vector<int> line;

		for ( unsigned int i = 0; i < buffer.length(); i++ )
		{
			line.push_back( buffer[i] - '0' );
		}

		for ( unsigned int i = 0; i < 9; i++ )
		{
			for ( unsigned int j = 0; j + 1 < line.size(); j++ )
			{
				line[j] = ( line[j] + line[j+1] ) % 10;
			}
		}

		cout << line[0] << endl;
	}

	return 0;
}

Measured memory_bytes: 0
#include <iostream>
    using namespace std;
     
    int main() {
    int N;
    cin>>N;
    long double sum=0.0;
    for(auto i=0; i<N; ++i)
    {
    long double p;
    string k;
    cin>>p>>k;
    if(k[0]=='B')
    {
    p=p*380000.0;
    }
     
    sum +=p;
    }
    cout <<sum<<endl;
    }


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    string a;
    cin >> a;
    if (a[0] == a[1] || a[1] == a[2] || a[2] == a[3])
        cout << "Bad";
    else
        cout << "Good";
    return 0;
}


Measured memory_bytes: 256
import Control.Monad (mplus)
import Data.List (transpose)
import Data.Maybe (fromMaybe)

main = do
  inputs <- fmap lines getContents
  mapM_ (putStrLn.(:[]).fromMaybe 'd'.winner.toField) inputs

toField :: String -> [String]
toField [] = []
toField str = take 3 str : toField (drop 3 str)

isWin :: Char -> [String] -> Maybe Char
isWin c f = horizon `mplus` vertical `mplus` closs
  where horizon = if (any id.map (all (== c)) $ f) then Just c
                                                   else Nothing
        vertical = if (any id.map (all (== c)) $ transpose f) then Just c
                                                              else Nothing
        closs = if (any id.map (all (== c)) $ getCloss f)  then Just c
                                                           else Nothing

getCloss f = [zipWith (!!) f [0,1,2], zipWith (!!) f [2,1,0]]

winner :: [String] -> Maybe Char
winner f = isWin 'o' f `mplus` isWin 'x' f `mplus` Nothing

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

int main(){
	int N,M;
	int a[100]; 
	int i=0;
	cin>>N>>M;
	for(int coun =0;coun<N;coun++){
		cin>>a[coun];
	}
	for(int k =1;k<=M;k++){
		i=0;
		while(true){			
			if((i+1)==N){
				break;
			}		
			if(((a[i]%k)>(a[i+1]%k))){
				int r;
				r = a[i+1];
				a[i+1]=a[i];
				a[i] = r;
			}
			i++;
		}
	}
	for(int coun =0;coun<N;coun++){
		cout<<a[coun]<<endl;
	}
}

Measured memory_bytes: 3096
n = int(input())
s = {}
for i in range(n):
    word = input()
    if(word in s):
        s[word] += 1
    else:
        s[word] = 1
m = int(input())
t = {}
for i in range(m):
    word = input()
    if(word in s):
        s[word] -= 1
a = []
for x in s:
    a.append(s[x])
ans = max(a)
if(ans < 0):
    print(0)
else:
    print(ans)


Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A, B, C, D;
		int t = 0;
		A = sc.nextInt();
		B = sc.nextInt();
		C = sc.nextInt();
		D = sc.nextInt();
		if (A <= C && C <= B) {
			if (B <= D) {
				t = B - C;
			} else {
				t = D - C;
			}
		} else if (C <= A && A <= D) {
			if (D <= B) {
				t = D - A;
			} else {
				t = B - A;
			}
		}
		System.out.println(t);
	}
}


Measured memory_bytes: 20948
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*);
    }
}

#[allow(unused_imports)]
use std::cmp::{min, max};

#[allow(unused_imports)]
use std::io::Write;

fn main() {
    input!{
      s: chars,
    }
    let mut cnt = vec![0; 28];
    for &c in s.iter() {
        cnt[(c as u8 - 'A' as u8) as usize] += 1;
    }

    for i in 0..28 {
        if cnt[i] != 0 && cnt[i] != 2 {
            println!("{}", "No");
            return
        }
    }
    println!("{}", "Yes");
}


Measured memory_bytes: 4352
#include <stdio.h>

int main(void) {
	int data[4][3][10] = {}; // data[i][j][k] : i?£?j???k??¨?±?
	int n;
	int b, f, r, v;
	int i, j, k;
	
	scanf("%d", &n);
	while (n--) {
		scanf("%d %d %d %d", &b, &f, &r, &v);
		b--; f--; r--;
		data[b][f][r] += v;
	}
	
	for (i = 0; i < 4; i++) {
		if (i) puts("####################");
		
		for (j = 0; j < 3; j++) {
			for (k = 0; k < 10; k++) {
				printf(" %d", data[i][j][k]);
			}
			puts("");
		}
	}
	
	return 0;
}

Measured memory_bytes: 608
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define Vi vector<int>
#define pb push_back
#define i197 1000000007
#define MAX_N 200002
using namespace std;

typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<Pii,int> Piii;
typedef pair<ll,int> Pli;
typedef pair<string,string> Pss;
const int inf=1000000000;
struct edge{
	int myc,to,c,cost;
};
struct pos{
	int to,cost,color;
};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main() {
	int n;
	ll a,s=0;
	vector<Pli> v;
	v.push_back(Pli(0,0));
	cin>>n;
	rep(i,n){
		cin>>a;
		s+=a;
		v.push_back(Pli(s,i+1));
	}
	sort(v.begin(),v.end());
//	rep(i,n+1)cout<<v[i].first<<" "<<v[i].second<<endl;
	int res=0;
	int k=0;
	rep(i,n){
		if(v[i].first==v[i+1].first){
			res=max(res,v[i+1].second-k);
		}else{
			k=v[i+1].second;
		}
	}
	cout<<res<<endl;
	return 0;
}



Measured memory_bytes: 7032
/*
  AtCoder Beginner Contest 087
  B - Coins
*/

#include<iostream>
using namespace std;

int A, B, C;
int X;

int main() {
  scanf("%d%d%d%d", &A, &B, &C, &X);

  int count = 0;
  for (int a = 0; a <= A; ++a) {
    for (int b = 0; b <= B; ++b) {
      for (int c = 0; c <= C; ++c) {
        if (500 * a + 100 * b + 50 * c == X) ++count;
      }
    }
  }

  printf("%d\n", count);
  return 0;
}

Measured memory_bytes: 256
N,M=map(int,input().split())
s=[list(map(int,input().split())) for _ in range(N)]
c=[list(map(int,input().split())) for _ in range(M)]
for i in range(N):
  d=10**9
  n=0
  for j in range(M):
    x=abs(s[i][0]-c[j][0])+abs(s[i][1]-c[j][1])
    if x<d:
      d=x
      n=j+1
  print(n)

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

int main() {
    int N,M;
    cin >> N >> M;
    string S;
    cin >> S;
    
    vector<int> ans;
    
    int pos = N;
    bool possible = true;
    while ( pos > 0 ){
        for ( int i = pos - M; i < pos; ++i){
            if ( i < 0 ) continue;
            else if ( S.at(i) == '0' ) {
                ans.push_back(pos-i);
                pos = i;
                break;
            } else if ( i == pos - 1 and S.at(i) == '1' ){
                possible = false;
                pos = 0;
                break;
            }
        }
    }
    
    
    
    
    if ( possible == false ){
        cout << -1 << endl;
    } else {
        int anssize = ans.size();
        for ( int i = 0; i < anssize; ++i){
            cout << ans.at(anssize - i - 1) << " ";
        }
        cout << endl;
    }
    
    return 0;
}



Measured memory_bytes: 1144
#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());
  bool b = false;
  for (int i = 0; i < N - 1; i++) {
    if(A[i] == A[i + 1]) {
        b = true;
        break;
    }
  }
  if (b) {
    cout << "NO" << endl;
  } else {
    cout << "YES" << endl;
  }
  return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<vector>
#include<functional>
#include<algorithm>
#include<cstdio>
using namespace std;
int main() {
	int a, b;
	char c;
	while (cin >> a >> c >> b&&c != '?') {
		if (c == '+') cout << a + b << endl;
		else if (c == '/') cout << floor(a / b) << endl;
		else if (c == '*')cout << a*b << endl;
		else cout << a - b << endl;
	}
}

Measured memory_bytes: 3224