akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;
int main() {
  int n;
  cin >> n;
  int a[n];
  int maxm = 0;
  int maxall = 0;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < n; i++) {
    if (i > 0 && a[i - 1] >= a[i]) {
      maxm += 1;
    } else {
      if (maxall < maxm) {
        maxall = maxm;
      }
      maxm = 0;
    }
  }
  if (maxm > maxall) {
    maxall = maxm;
  }
  cout << maxall << endl;
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
using namespace std;
using ll = long long;



int main() {
	int x;
	cin >> x;
	if (x == 3 || x == 5 || x == 7) cout << "YES" << endl;
	else cout << "NO" << endl;

	return 0;
}


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

using namespace std;

int main(){

    int A, B, C;
    cin >> A >> B >> C;
    int K;
    cin >> K;
    for(int i = 0; i < K; i++){
        if(A >= B){
            B *= 2;
        }
        else if(B >= C){
            C *= 2;
        }
    }

    if(A < B && B < C){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 3628
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <regex>
#define ull unsigned long long
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,j,n) for(int i = j; i < n; i++)
#define RFOR(i,j,n) for(int i = j-1; i >= n; i--)
#define PREC(n) fixed << setprecision(n)
#define print_array(v) REP(__k, v.size()) { cout << v[__k]; if(__k != v.size()-1) cout << " "; else cout << endl; } value
#define YesorNo(a) printf(a?"Yes\n":"No\n")
using namespace std;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int a,b; 
	cin>>a>>b;
	int ans=0,C=1;
	while(C<b){
		C+=a-1;
		ans++;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
int main() {
  int a;
  int b;
  int age;
  scanf("%d",&age);
  if (age == 1)	{
    printf("Hello World\n");
  } else {
    scanf("%d %d",&a,&b);
    printf("%d\n",a+b);
  }
  return 0;
}

Measured memory_bytes: 128
var
 s,x:ansistring; 
 k:longint;
begin
 readln(s);
 k:=pos('C',s);
 if k=0 then begin writeln('No'); halt; end;
 x:=copy(s,k+1,length(s));
 if pos('F',x)<>0 then writeln('Yes')
                            else writeln('No');
end.

Measured memory_bytes: 128
import java.util.Scanner;

class Main{
	public static void main(String[] args) {
		try(Scanner sc = new Scanner(System.in)){
			StringBuilder str = new StringBuilder(sc.next());
			int q = sc.nextInt();
			
			for(int i=0;i<q;i++) {
				String op = sc.next();
				int a = sc.nextInt();
				int b = sc.nextInt();
				
				if(op.contentEquals("replace")) {
					str.delete(a, b+1);
					str.insert(a, sc.next());
				}else if(op.contentEquals("reverse")) {
					str.replace(a, b+1,new StringBuilder(str.substring(a,b+1)).reverse().toString());
				}else if(op.contentEquals("print")) {
					System.out.println(str.substring(a,b+1));
				}
			}
		}
	}
}


Measured memory_bytes: 29324
#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#define debug(x) cerr << #x << ':' << x << endl
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define ALL(c) (c).begin(), (c).end()
using namespace std;
typedef long long ll;

int main(){
    string s1, s2;
    cin >> s1 >> s2;
    string tmp = s1+s1;
    
    if(tmp.find(s2)!=string::npos)  cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3224
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i=0;i<n;i++)
void chmax(int& a,int b){a=max(a,b);}

int dp[2005][2005];

int main(){
    int n;cin>>n;
    int n3=n*3;
    vector<int> A(n3);
    rep(i,n3)cin>>A[i],--A[i];
    rep(i,n+1)rep(j,n+1)dp[i][j]=-1e9;
    auto upd=[&](int i,int j,int x){
        chmax(dp[i][j],x);
        chmax(dp[j][i],x);
        chmax(dp[i][n],x);
        chmax(dp[n][i],x);
        chmax(dp[j][n],x);
        chmax(dp[n][j],x);
        chmax(dp[n][n],x);
    };
    //いろんな更新の仕方があり、それらの更新のうち最大のものになるような更新手法
    upd(A[0],A[1],0);
    
    int base=0;
    for(int ai=2;ai<n3-1;ai+=3){
        int x=A[ai],y=A[ai+1],z=A[ai+2];
        if(x==y&&y==z){
            ++base;
            continue;
        }//(x==y==z)ならどの(a,b)についてもdp[a][b]は+1で更新される。
        //そうでない時はdp[a][b]について、x,y,zを取り除いた場合を考えるとどれも無更新
        //よって,べつの取り除き方での最大値の更新のみを考えればいい
        vector<tuple<int,int,int>> q;
        rep(ri,3){
            {
                rep(a,n){
                    int now=dp[a][n];
                    if(y==z)chmax(now,dp[a][y]+1);
                    q.emplace_back(a,x,now);
                }
            }
            int now=max(dp[n][n],dp[z][z]+1);
            q.emplace_back(x,y,now);
            swap(x,y);swap(y,z);
        }
        for(auto t:q){
            int i,j,x;
            tie(i,j,x)=t;
            upd(i,j,x);
        }
    }
    int ans=dp[n][n];
    int l=A[n3-1];
    chmax(ans,dp[l][l]+1);
    ans+=base;
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 19456
#include<string>
#include<iostream>
#include<algorithm>
#include<set>
#include<math.h>
#include<vector>
#include<sstream>
#include<queue>
#include<functional>
#include<bitset>
#include<cstdio>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include <string.h>
using ll = long long;
 
#define rep(i, n) for(ll i = 0; i < (int)(n); i++)
#define reps(i,x) for(ll i=1;i<=(int)(x);i++)
#define rrep(i,x) for(ll i=((int)(x)-1);i>=0;i--)
#define rreps(i,x) for(ll i=(int)(x);i>0;i--)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define vll vector<ll>
#define vi vector<int>
#define mp make_pair
#define vpll vector<pair<ll,ll>>
#define vpi vector<pair<int,int>>
#define mod 1000000007 
using namespace std;
int a[501][501];
string ans[250001];

int main() {
  string s;
  cin >> s;
  sort(all(s));
  if(s == "abc"){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}


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

int main()
{
  int a,b,c;
  cin >> a >> b >> c;
  if(a==b) cout << c << endl;
  else if(a==c) cout << b << endl;
  else if(b==c) cout << a << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <bitset>
#include <algorithm>
#include <iomanip>

using namespace std;

#define forn(i,n) for (int i = 0; i < int(n); i++)
#define ford(i,n) for (int i = int(n) - 1; i >= 0; i--)
#define fore(i,l,r) for (int i = int(l); i <= int(r); i++)
#define all(a) a.begin(), a.end()
#define sz(a) int(a.size())
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define x first
#define y second

template<typename X> inline X abs(const X& a) { return a < 0 ? -a : a; }
template<typename X> inline X sqr(const X& a) { return a * a; }

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;
const ld PI = acosl(ld(-1));

const int N = 100 * 1000 + 3;
int n;
int a[N];

inline bool read()
{
	if (scanf ("%d", &n) != 1)
		return false;
		
	forn (i, n)
	{
		assert(scanf ("%d", &a[i]) == 1);
		
		a[i]--;
	}

	return true;
}

inline void solve()
{
	int ans = 0;
	forn (i, n)
	{
		int j = a[i];
		if (a[j] == i)
			ans++;
	}
	
	cout << ans / 2 << endl;
}

int main()
{
#ifdef SU2_PROJ
	assert(freopen("input.txt", "r", stdin));
	assert(freopen("output.txt", "w", stdout));
#endif

	cout << setprecision(25) << fixed;
	cerr << setprecision(10) << fixed;

	srand(int(time(NULL)));

	assert(read());
	solve();

#ifdef SU2_PROJ
	cerr << "TIME: " << clock() << endl;
#endif

	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
#define era(t) t.erase(unique(be(t)),t.end())
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;
typedef long long ll;
using namespace std;
const ll mod=1000000007,mod9=1000000009;
template <class T>inline T lcm(T a,T b){return (a*b/__gcd(a,b));}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,m;
    cin>>n>>m;
    ll a,b,x=0,y=1e9;
    for(int i=0;i<m;i++){
        cin>>a>>b;
        x=max(x,a);
        y=min(y,b);
    }
    ll ans=(y-x+1<0)?0:y-x+1;
    cout << ans <<endl;


    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <utility>
#include <algorithm>
#include <cmath>
#include <climits>
#include <iomanip>
#include <queue>
#include <stack>

using namespace std;

typedef long long ll;

int main() {
    int a, b;
    cin >> a >> b;
    cout << a * b << endl;
    return 0;
}

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

int compare_int(const void *a, const void *b){
    return *(int*)a - *(int*)b;
}

int main(){
    int N,*X,*tmp,i,l,r;
    cin >> N;
    X = new int[N];
    tmp = new int[N];
    for(i=0;i<N;i++){
        cin >> X[i];
        tmp[i] = X[i];
    }
    qsort(tmp,N,sizeof(int),compare_int);
    l = tmp[(N/2)-1];
    r = tmp[N/2];
    for(i=0;i<N;i++){
        if(X[i]<=l){
            cout << r << endl;
        }else{
            cout << l << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 3820
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
#include<vector>
#include<stack>
#include<math.h>
#include<queue>
#include<complex>
#include<random>
#include<ctime>
using namespace std;



const long long int mod=1000000007;
const long long int INF=99999999999999999;
long long int mode=0;
string s,t;

long long int h,w,d,a[310][310],q,L[120000],R[120000],mp_consumption[100000];
pair<long long int,long long int>ij[300005];

int main() {
	cout << fixed << setprecision(18);
    cin>>h>>w>>d;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin>>a[i][j];
            ij[a[i][j]]={i,j};
        }
    }
    cin>>q;
    for(int i=1;i<=d;i++){
        mp_consumption[i]=0;
        long long int now=i+d;
        while(now<=h*w){
            mp_consumption[now]=mp_consumption[now-d]+abs(ij[now].first-ij[now-d].first)+abs(ij[now].second-ij[now-d].second);
            now+=d;
        }
    }
    for(int i=0;i<q;i++){
        cin>>L[i]>>R[i];
        cout<<mp_consumption[R[i]]-mp_consumption[L[i]]<<endl;
    }
} 


Measured memory_bytes: 6272
a,b,c = gets.split.map(&:to_i)
k = gets.to_i

def f(a,b,c,k)
  if a < b && b < c
    puts 'Yes'
    exit 0
  end
  if k == 0
    return
  end
  f(a,b*2,c,k-1)
  f(a,b,c*2,k-1)
end

f(a,b,c,k)
puts 'No'



Measured memory_bytes: 14352
#include<bits/stdc++.h>
#define LLI long long int
#define pii pair<int,int>
#define fst first
#define sec second
#define ULTRA 2134567890
#define de(x) if(x!=0 && MODE==x)
#define MODE 1
using namespace std;

int main()
{
    int i,j,h;
    int K;

    scanf("%d", &K);

    LLI ans = 0;
    for( i=1; i<=K; i++)
    {
        for( j=1; j<=K; j++)
        {
            for( h=1; h<=K; h++)
            {
                int gcd = __gcd( i,j);
                gcd = __gcd( gcd, h);
                ans += gcd;
            }
        }
    }

    printf("%lld\n", ans);

    return 0;
}

//
//          ___ ___  __________  __________
//         /////\  \/\   ______\/\\\\\\\\\\\  Code by ~Ice Tea~ of
//        //// \ \  \ \  \_____/\ \\\\_____/      New Empire of CHSH ...
//       ////   \ \  \ \  \      \ \\\\\\\\\\\
//      ////__   \ \  \ \  \      \ \\\\_____/
//     ///////\   \ \  \ \  \______\ \\\\_______   ________
//    ////____/    \ \__\ \___   ___\ \\\\\\\\\\\ _\  ___  \_
//   /__/           \/__/\/__/\  \__/\ \\\\_____//\  .\_/\_  \
//                           \ \  \   \ \\\\\\\\\\\\  \_\/_\  \
// ... with the AC Power of   \ \  \   \ \\\\_____/ \   _____  \
//   The Great Tsundere Doggy. \ \  \   \ \\\\     \ \  \  \ \  \
//                              \ \__\   \ \\\\\\\\\\ \__\  \ \__\
//                               \/__/    \/________/\/__/   \/__/
//


Measured memory_bytes: 3832
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<ll,ll> P;
typedef pair<ll,pair<ll,ll>> p;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
static const int MAX_SIZE = 1 << 17; //segment tree のサイズ。この実装では2べきにする必要がある。 2^17 ≒ 1.3 * 10^5

int C[30];

int main(){
    bool flagT[110000],flagA[110000];
    ll A[110000],T[110000];
    int N;
    cin>>N;

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

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

    for(int i=2;i<=N;i++){
        if(T[i]>T[i-1]) flagT[i]=true;
        else flagT[i]=false;
    }

    for(int i=N-1;i>=1;i--){
        if(A[i]>A[i+1]) flagA[i]=true;
        else flagA[i]=false;
    }

    flagT[1]=true;
    flagA[N]=true;
    ll ans=1;
    for(int i=1;i<=N;i++,ans%=MOD){
        if(flagA[i] && flagT[i]){
            if(A[i]!=T[i]){
                cout<<0<<endl;
                return 0;
            }
        }else if(!flagA[i] && !flagT[i]){
            ans*=min(A[i],T[i]);
        }else{
            if(flagA[i] && A[i]>T[i] || flagT[i] && T[i]>A[i]){
                cout<<0<<endl;
                return 0;
            }
        }
    }
    cout<<ans<<endl;
}



Measured memory_bytes: 2048
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE RankNTypes #-}
import Control.Monad.ST
import Data.Array.ST
import Control.Arrow
import Control.Monad
import Data.List
import qualified Data.ByteString.Char8 as B

main :: IO ()
main = readLine >>= main'
    where
        main' [n, m] = readContents m >>= print . solve n . map (map pred)

solve :: Int -> [[Int]] -> Int
solve n es = length . filter id $ runST stRes
    where
        cs = build [] es

        stRes :: forall s. ST s [Bool]
        stRes = mapM stAction cs

        stAction :: [[Int]] -> forall s. ST s Bool
        stAction xs = makeTree n >>= connect xs >>= size 0 >>= check 

        build xs (y : ys) = (xs ++ ys) : build (y : xs) ys
        build _ _ = []

        connect xs uft = uft <$ mapM_ (\[a, b] -> unionNodes a b uft) xs 

        check s = return $ s /= n

                

readLine :: IO [Int]
readLine = unfoldr (fmap (second (maybe B.empty snd . B.uncons)) . B.readInt) <$> B.getLine

readContents :: Int -> IO [[Int]]
readContents = flip replicateM readLine

type UFTree s = STArray s Int (Int, Int)

makeTree :: Int -> ST s (UFTree s)
makeTree n = newListArray (0, n - 1) . zip [0..(n - 1)] $ repeat 1

findRoot :: Int -> UFTree s -> ST s (Int, Int)
findRoot v uft = readArray uft v >>= check
    where
        check res@(root, _)
            | v == root = return res
            | otherwise = findRoot root uft >>= edit
        edit res = res <$ writeArray uft v res
            
unionNodes :: Int -> Int -> UFTree s -> ST s ()
unionNodes a b uft = mapM (`findRoot` uft) [a, b] >>= check
    where
        check [(c, cs), (d, ds)]
            | c == d = return ()
            | cs < ds = writeArray uft c (d, cs + ds) >> writeArray uft d (d, ds + cs)
            | otherwise = writeArray uft d (c, cs + ds) >> writeArray uft c (c, cs + ds) 

isSame :: Int -> Int -> UFTree s -> ST s Bool
isSame a b uft = (== 1) . length . group <$> mapM (\v -> fst <$> findRoot v uft) [a, b]

size :: Int -> UFTree s -> ST s Int 
size v uft = snd <$> findRoot v uft

Measured memory_bytes: 892
# ABC 073 D
import itertools

N, M, R = map(int,input().split())
s = list(map(int,input().split()))
D = [[10**9+7 for k in range(N)] for l in range(N)]
for k in range(N):
    D[k][k] = 0
for k in range(M):
    A, B, C = map(int,input().split())
    A -= 1
    B -= 1
    D[A][B] = C
    D[B][A] = C

for p in range(N):
    for q in range(N):
        for r in range(N):
            D[q][r] = min(D[q][r], D[q][p]+D[p][r])

cities = list(itertools.permutations(s))
ans = 10**9+7
for p in cities:
    t = 0
    for k in range(R-1):
        t += D[p[k]-1][p[k+1]-1]
    ans = min(ans,t)

print(ans)

Measured memory_bytes: 55512
#include <bits/stdc++.h>
using namespace std;
const unsigned int MOD = 1000000007;
#define ll long long
#define PI 3.1416
string day[]={"SUN","MON","TUE","WED","THU","FRI","SAT"};
int main() {
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int a,b;
    while(cin>>a>>b){
        if(a%3==0 || b%3==0 || (a+b)%3==0)cout<<"Possible"<<endl;
        else cout<<"Impossible"<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ld long double
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; }
using P=pair<long long,long long>;
#define rep(i,n) for(long long i=0; i<(long long)n; i++)
#define req(i,n) for(long long i=n-1; i>=0; i--)
#define range(i,a,b) for(long long i=a; i<b; i++)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((long long)(x).size())
#define COUT(x) cout << x << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define onBoard(y,x) (y>=0 && y<h && x>=0 && x<w)
#define vint vector<int>
#define pri_que priority_queue
#define vvint vector<vector<int>>
#define vstr vector<string>
#define vp vector<pair<int,int>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define SUM(x) accumulate(x.begin(),x.end(),0)
#define MAX(x) *max_element(x.begin(),x.end())
#define MIN(x) *min_element(x.begin(),x.end())
#define couty cout<<"Yes"<<endl
#define coutn cout<<"No"<<endl
#define coutY cout<<"YES"<<endl
#define coutN cout<<"NO"<<endl
#define yn(x) cout<<(x?"Yes":"No")<<endl
#define YN(x) cout<<(x?"YES":"NO")<<endl
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
long long lcm(long long a, long long b){return a*b/gcd(a,b);}
const long long dx[8]={1,0,-1,0,1,-1,-1,1};
const long long dy[8]={0,1,0,-1,1,1,-1,-1};
const long long INF = 1e12;
const long long MOD = 1e9+7;

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(15);

    int n; cin >> n;
    vstr s(n);
    int a=0,b=0,ab=0;
    rep(i,n){
        cin >> s[i];
        if(s[i][0]=='B' && s[i][s[i].size()-1]=='A') ab++;
        else if(s[i][0]=='B') b++;
        else if(s[i][s[i].size()-1]=='A') a++;
    }
    int res=0;
    rep(i,n){
        rep(j,s[i].size()-1){
            if(s[i].substr(j,2)=="AB") res++;
        }
    }
    if(ab==0) cout<<res+min(a,b)<<endl;
    else if(a+b>0) cout<<res+ab+min(a,b)<<endl;
    else if(a+b==0) cout<<res+ab-1<<endl;

}

Measured memory_bytes: 3704
N, W = map(int, input().split())
w, v = [], []
for _ in range(N):
    w_, v_ = map(int, input().split())
    w.append(w_)
    v.append(v_)
V = sum(v)
dp = [[float("INF")]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(V+1):
        if j >= v[i]: dp[i+1][j] = min(dp[i][j] ,dp[i][j-v[i]]+w[i])
        else: dp[i+1][j] = dp[i][j]
ans = 0
for i in range(V+1):
    if dp[N][i]<=W: ans=i
print(ans)

Measured memory_bytes: 307832
#include <stdio.h>

#define H 500000

int left(int);
int right(int);
void maxHeapify(int*,int);
void buildMaxHeap(int*);

int n;

int main(){

 int i;
 int p;
 int l;
 int r;
 int A[H];

 scanf("%d",&n);

 for(i=1;i<=n;i++){
 scanf("%d",&A[i]);
 }

 buildMaxHeap(A);

 for(i=1;i<=n;i++){
   printf(" %d",A[i]);
 }

 printf("\n");

 return 0;
}

int left(int i){
 return 2 * i;
}

int right(int i){
 return 2 * i + 1;
}

void maxHeapify(int *A,int i){

  int l;
  int r;
  int tmp;
  int largest;

  l = left(i);
  r = right(i);

  if(l<=n && A[l]>A[i]){
    largest = l;
  }

  else{
    largest = i;
  }

  if(r<=n && A[r]>A[largest]){
    largest = r;
  }

  if(largest!=i){
    tmp = A[i];
    A[i] = A[largest];
    A[largest] = tmp;
    maxHeapify(A,largest);
  }
}

void buildMaxHeap(int *A){
  int i;
  for(i=n/2;i>=1;i--){
    maxHeapify(A,i);
  }
}

Measured memory_bytes: 2552
#include<stdio.h>

int main(void){
	int a,b,c;
	int x;
	
	scanf("%d %d %d",&a,&b,&c);
	
	if(b<a){
		x=b;
		b=a;
		a=x;
	}
	
	if(c<b){
		x=c;
		c=b;
		b=x;
	}
	
		if(b<a){
		x=b;
		b=a;
		a=x;
	}

	printf("%d %d %d\n",a,b,c);
	
	return 0;
}

Measured memory_bytes: 596
<?php
fscanf(STDIN,'%d %d',$N,$M);
//1ゲート目、全ゲート通過できるカード番号の最小値/最大値を求める
fscanf(STDIN,'%d %d',$L,$R);
$min = $L;
$max = $R;
//2ゲート目以降
for($i=2;$i<=$M;$i++){
  fscanf(STDIN,'%d %d',$L,$R);
  if($L>$min){
    $min = $L;
  }
  if($max>$R){
    $max = $R;
  }
  //最小値が最大値を超えたら通過できるカードなし
  if($min>$max){
    $min = 1;
    $max = 0;
    break;
  }
}
//最小値自身のカード番号を引かないよう最小値-1を引く
echo $max-($min-1);

Measured memory_bytes: 3828
#include<algorithm>
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<stack>
#include<cmath>
#include<list>
#include<set>
#include<map>

using namespace std;
long long MOD = 1000000007LL;

int main() {
	int N, X;
	cin >> N;
	X = N / 1.10;
	for (int i = X; i <= N; ++i) {
		if (floor(i * 1.08) == N) {
			cout << i << endl;
			return 0;
		}
	}
	cout << ":(" << endl;

	return 0;
}

Measured memory_bytes: 256
#[allow(unused_macros)]
macro_rules! invec {
    ( $t:ty ) => {{
        let mut s = String::new();
        match std::io::stdin().read_line(&mut s) {
            Ok(0) => Vec::<$t>::new(),
            Ok(n) => s.trim().split_whitespace().map(|s| s.parse::<$t>().unwrap()).collect::<Vec<$t>>(),
            Err(_) => Vec::<$t>::new(),
        }
    }}
}

#[allow(unused_macros)]
macro_rules! input {
    ( $($t:ty),* ) => {{
        let mut s = String::new();
        std::io::stdin().read_line(&mut s);
        let mut splits = s.trim().split_whitespace();
        ($(
            {
                 splits.next().unwrap().parse::<$t>().unwrap()
            },
        )*)
    }}
}

#[allow(unused_must_use)]
#[allow(unused_variables)]
fn solve() {
    let (_,) = input!(usize);
    let mut dmap = std::collections::HashMap::<u32, u32>::new();
    let dv = invec!(u32);
    for val in dv {
        let hash = dmap.entry(val).or_insert(0);
        *hash += 1;
    }

    let (_,) = input!(usize);
    let tv = invec!(u32);
    for val in tv {
        if let Some(hash) = dmap.get_mut(&val) {
            if *hash == 0 {
                println!("NO");
                std::process::exit(0);
            }
            *hash -= 1;
        } else {
            println!("NO");
            std::process::exit(0);
        }
    }
    println!("YES");
}

fn main() {
    solve();
}


Measured memory_bytes: 13488
{-# LANGUAGE OverloadedStrings, BangPatterns #-}
import Control.Arrow
import Control.Monad.Fix
import Data.Char
import Data.Int
import Data.Foldable
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as VU
import qualified Data.ByteString.Char8 as B
import Debug.Trace

solve :: Int -> Int -> B.ByteString
solve !a !b | isMonth a && isMonth b       = "AMBIGUOUS"
            | isMonth a && not (isMonth b) = "MMYY"
            | isMonth b && not (isMonth a) = "YYMM"
            | otherwise                    = "NA"
 where
  isYear n = True
  isMonth n = n >= 1 && n <= 12

main = do
  let readInt :: Integral a => B.ByteString -> Maybe (a, B.ByteString)
      readInt = fmap (first fromIntegral . second B.tail) . B.readInt

  s <- B.getLine
  B.putStrLn $ solve ((\(Just (x, _)) -> x) $ readInt $ B.take 2 s)
                     ((\(Just (x, _)) -> x) $ readInt $ B.drop 2 s)


Measured memory_bytes: 380
N=int(input())
s=[input() for i in range(N)]
c=0
if(len(s)!=len(set(s))):
  c=1
else:
  for i in range(N-1):
    if(s[i][-1]!=s[i+1][0]):
      c=1
      break
    else:continue
if(c==0):
	print('Yes')
else:print('No')

Measured memory_bytes: 3060
import java.util.Scanner;

class Main{
  String[] data = new String[200];
  int num;

  Main(){
    this.num = 0;
  }

  boolean push(String c){
    if(this.isFull())
      return false;
    else{
      this.data[++num] = c;
      return true;
    }
  }

  String pop(){
    return this.data[num--];
  }

  boolean isFull(){
    return num == 199;
  }

  boolean isEmpty(){
    return num == 0;
  }


  public static void main(String[] args){
    Scanner stdIn = new Scanner(System.in);
    int ans;
    int ope1, ope2;
    Main stack = new Main();

    while(stdIn.hasNext()){
      String input = stdIn.next();
      if(input.equals("+") || input.equals("-") || input.equals("*")){
        ope2 = Integer.parseInt(stack.pop());
        ope1 = Integer.parseInt(stack.pop());
          if(input.equals("+"))
            ans = ope1 + ope2;
          else if(input.equals("-"))
            ans = ope1 - ope2;
          else
            ans = ope1 * ope2;
        stack.push(Integer.toString(ans));
      }
      else{
        stack.push(input);
      }
    }

  
    System.out.println(stack.pop());
  }
}

Measured memory_bytes: 26192
#include <bits/stdc++.h>
#define re return
#define ull unsigned long long
#define ll long long
#define ld long double
#define oo 1e9
#define pi 3.1415926536
#define OO 1e18
#define EPS 1e-7
#define FX(n) fixed<<setprecision(n)
#define mm(o,k) memset(o,k,sizeof o)
#define Hossam_Yehia ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
int n,p,x,arr[55];
ll DP[55][2];
ll dp(int i,int sum){
    if(i==n)re sum==p;
    ll &ret=DP[i][sum];
    if(~ret)re ret;
    re ret=dp(i+1,(sum+arr[i])%2)+dp(i+1,sum);
}
int main(){
    Hossam_Yehia;
    cin >> n >> p;
    for(int i=0;i<n;++i)cin>>arr[i];
    mm(DP,-1);
    cout<<dp(0,0)<<endl;
    re 0;
}

Measured memory_bytes: 256
//============================================================================
// Name        : JOI.cpp
// Author      : Akari Fujii
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cctype>
#include <string>
#include<algorithm>

using namespace std;
typedef long long ll;

// 1. dp?????????
ll dp[100001];
// 2. n????????????
ll n,t,q;
ll a[100001],d[100001],x;

// ???. calc????????????
ll calc(ll k){
	// 8. dp???????????°??????
	if(dp[k]!=a[k])return dp[k];

	if(d[k]==1){
		if(d[k+1]==1){
			dp[k]=min(calc(k+1),a[k]+t);
		}else{
			dp[k]=min(a[k]+t,(a[k]+a[k+1])/2);
		}
	}else if(d[k]==2){
		if(d[k-1]==2){
			dp[k]=max(calc(k-1),a[k]-t);
		}else{
			dp[k]=max(a[k]-t,(a[k]+a[k-1])/2);
		}
	}
	return dp[k];
}

int main() {

	cin>>n>>t>>q;

	// 3. ?????????
	for(int i=0;i<100001;++i){
			dp[i]=-1;
	}

	// 4.??\???
	for(int i=1; i<n+1; ++i){
		cin>>a[i]>>d[i];
		dp[i]=a[i];
	}


	// 5. ???????????¨??????
	if(d[1]==2){
		dp[1]=a[1]-t;
	}
	if(d[n]==1){
		dp[n]=a[n]+t;
	}

	// 6. ??????
	for(int i=0; i<q; ++i){
		cin>>x;
		cout<<calc(x)<<endl;
	}

	return 0;

}

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

int main() {
  string S;
  cin>>S;
  int count=0;
  
  for(int i=0;i<4;i++){
    if(S.at(i)=='+'){
      count++;
    }
    else{
      count--;
    }
  }
  cout<<count<<endl;
  
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define dunk(a) cout << (a) << "\n"
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int inf = 1001001001;
const int mod = 1000000007;

int modPow(long long a, long long n, long long p) {
	if (n == 1) return a % p;
	if (n % 2 == 1) return (a * modPow(a, n - 1, p)) % p;
	long long t = modPow(a, n / 2, p);
	return (t * t) % p;
}

int res[100001];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n; cin >> n;
	if (n == 1) {
		int p; cin >> p;
		if (p == 0) dunk(1);
		else dunk(0);
		return 0;
	}
	vector<int> a(n);
	rep(i, n) cin >> a[i];

	if (n % 2 == 0) {
		rep(i, n) {
			res[a[i]]++;
		}
		bool elf = true;
		rep(i, n) {
			if (res[i] == 2) {
				if (i % 2 == 0) elf = false;
			}
			else if (res[i] != 0) elf = false;
		}
		if (elf) {
			int ans = modPow(2, n / 2, mod);
			dunk(ans);
		}
		else {
			dunk(0);
		}
	}
	else {
		rep(i, n) {
			res[a[i]]++;
		}
		bool elf = true;
		rep(i, n) {
			if (res[i] == 2) {
				if (i % 2 != 0) elf = false;
			}
			else if (res[i] != 0) {
				if (i != 0) elf = false;
			}
		}
		if (elf) {
			int ans = modPow(2, (n - 1) / 2, mod);
			dunk(ans);
		}
		else {
			dunk(0);
		}
	}

	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const  ll INF = 1e9;
const  ll MOD = 1e9 + 7;
#define all(v) v.begin(), v.end()
#define repi(i,n,init) for(ll i=init;i<(n);i++)
#define repd(i,n,init) for(ll i=(n);i>=init;i--)
#define repm(i,m) for(auto i=m.begin();i!=m.end();i++)
#define repb(bit,n,init) for(ll bit=init;bit<(1<<n);++bit)

int main()
{
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    while(true){
        c -= b;
        if(c <= 0){
            cout << "Yes" << endl;
            return 0;
        }
        a -= d;
        if(a <= 0){
            cout << "No" << endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace std;
using namespace __gnu_pbds;
typedef tree<
        pair<int, int>, // change type
        null_type,
        less<pair<int, int> >, // change type
        rb_tree_tag,
        tree_order_statistics_node_update>
        ordered_set;

typedef long long ll;
#define rep(i, start, end) for(int i = start; i < end; ++i)
#define per(i, start, end) for(int i = (int)start-1; i >= end; --i)
#define sz(x) (int)(x).size()
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(d, v) memset(d, v, sizeof(d))
#define pii pair<int, int>
const double PI = 3.14159265358979323846;
const double eps = (1e-8);


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
//#ifndef ONLINE_JUDGE
//    freopen("input.txt", "r", stdin);
////    freopen("facebook.txt", "w", stdout);
//#endif
    int n, w, h;
    cin >> n >> w >> h;
    cout << (n - w + 1) * (n - h + 1) << '\n';
    return 0;
}

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

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

    for(int i = 1; i <= 9; i++) {
        if(n % i == 0 && n / i < 10 ) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef		 long long int    ll;
typedef		vector<ll>      vll;
#define     fi              first
#define     se              second
#define		pb              push_back
#define		nn              "\n"
#define		all(p)          p.begin(),p.end()
#define		zz(v)           (ll)v.size()
#define 	S(a)            scanf("%lld",&a)
#define 	SS(a,b)         scanf("%lld %lld",&a,&b)
#define 	SSS(a,b,c)      scanf("%lld %lld %lld",&a,&b,&c)
#define		ss              ' '
#define     pii             pair<ll,ll>
#define		gcd(a,b)        __gcd(a,b)
#define		lcm(a,b)        (a*b)/gcd(a,b)
const double eps = 1e-8;



int main()
{
    ll n;
    cin>>n;
    string s;
    cin>>s;
    ll i=n-1;
    while(i>=0&&s[i]=='W')
        i--;

    ll ans=0;
    ll w=0;
    for(ll j=0; j<=i; j++)
        if(s[j]=='W')
            w++;
    if(w<=0)
    {
        cout<<0<<nn;
        return 0;
    }
    while(1)
    {
        if(w<=0)
            break;
        ll c=0;
        while(i>=0&&s[i]=='R')
            i--,c++;
        if(c<w)
        {
            ans+=c;
            w-=c;
        }
        else
        {
            ans+=w;
            break;
        }

        while(i>=0&&s[i]=='W')
            i--,w--;



    }
    cout<<ans<<nn;



}


/* Final check before submit :

1. array size or integer overflow,like uninitialised 0 index.

2. Think twice,code once.check all possible counter test case.

3. Be careful about corner case! n=1?k=1? something about 0?

4. avoid stupid mistake!complexity(t/m)?precision error?submit same code twice?

5. if got WA than remember that you are missing something common.
   *** Be confident!!! who knows? may be your one step back to AC ***

*/





Measured memory_bytes: 3764
import sys
input = sys.stdin.readline

N, M = map(int,input().split())
PY = [list(map(int, input().split()))+[i] for i in range(M)]


PY.sort(key=lambda x: (x[0],x[1]))
ans = []
num = 1
for i in range(M):
    if i>0 and PY[i][0] != PY[i-1][0]:
        num = 1
    ken = str(PY[i][0]).zfill(6)
    shi = str(num).zfill(6)
    ans.append([PY[i][2],ken+shi])
    num+=1
ans.sort()
for i in range(M):
    print(ans[i][1])


Measured memory_bytes: 41528
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <deque>

using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, int> pli;
const int MAXN = 345;
const LL INF = (LL)1e18;
LL dis[MAXN], A[MAXN][MAXN];
bool visit[MAXN];
vector<pii> G[MAXN];
struct node{
       int x, y;
       LL cost;
       node (int a, int b, LL c) : x(a), y(b), cost(c) {}
       bool operator < (const node &a) const {
            return cost < a.cost;
       }
};

int check(int x, int y, LL cost, int N) {
    LL cand = INF;
    for (int i = 0; i < N; i++) {
        if (i == x || i == y) continue;
        cand = min(cand, A[x][i] + A[i][y]);
    }
    if (cand < cost) return 0;
    else if (cand == cost) return 1;
    else return 2;
}

int main() {
    int N;
    scanf("%d", &N);
    vector<node> cand;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%lld", &A[i][j]);
            if (i >= j) continue;
            cand.push_back(node(i, j, A[i][j]));
        }
    }
    sort(cand.begin(), cand.end());
    bool OK = true;
    LL sum = 0;
    for (auto i : cand) {
        int chk = check(i.x, i.y, i.cost, N);
        if (!chk) OK = false;
        else if (chk == 2) sum += i.cost;
    }
    if (!OK) sum = -1;
    printf("%lld\n", sum);
    return 0;
}


Measured memory_bytes: 2036
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> Pii;

ll X;

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

int main() {
    cin >> X;

    ll ans_A = -1, ans_B = -1;
    for (ll a = -1000; a <= 1000; a++) {
        for (ll b = -1000; b <= 1000; b++) {
            if (pow(a, 5) - pow(b, 5) == X) {
                ans_A = a;
                ans_B = b;
            }
        }
    }
    /*
    for (ll b = -1.0e3; b < 1.0e3; b++) {
        double a_a = pow(X+pow(b, 5), 0.2);
        cout << a_a << " " << (ll)a_a << endl;
        if (abs(a_a - (ll)(a_a)) < eps) {
            ans_A = (ll)a_a;
            ans_B = b;
        }
    }
*/
    /*
    vector<ll> div = divisor(X);
    for (int i = 0; i < div.size(); i++) {

        for (ll  b = -1.0e6; b < 1.0e6; b++) {
            ll a = div[i] + b;
            if (a*a*a*a + a*a*a*b + a*a*b*b + a*b*b*b + b*b*b*b == X/div[i]) {
                ans_A = a;
                ans_B = b;
            }
        }
    }
*/

    cout << ans_A << " " << ans_B << endl;

    
    return 0;
}


Measured memory_bytes: 4072
s = list(input())
s.pop()

for i in range(len(s)):
    if len(s)%2 == 0:
        a,b = s[0:len(s)//2],s[len(s)//2:]
        if a == b:
            print(len(s))
            break
        else:
            s.pop()
    else:
        s.pop()

Measured memory_bytes: 3060
h, w = map(int,input().split())
s_l = []
for i in range(h):
    s_l.append(list(input()))
    for j in range(w):
        if s_l[i][j] == '.':
            s_l[i][j] = 0
        else:
            s_l[i][j] = 1

dp = []
for _ in range(h):
    dp.append([0] * w)

if s_l[0][0] != 0:
    dp[0][0] += 1

for i in range(1,h):
    if dp[i-1][0]%2 != s_l[i][0]:
        dp[i][0] = dp[i-1][0] + 1
    else:
        dp[i][0] = dp[i-1][0]
for j in range(1,w):
    if dp[0][j-1]%2 != s_l[0][j]:
        dp[0][j] = dp[0][j-1] + 1
    else:
        dp[0][j] = dp[0][j-1]

for i in range(1,h):
    for j in range(1,w):
        if dp[i-1][j]%2 != s_l[i][j]:
            plus_i = 1
        else:
            plus_i = 0
        if dp[i][j-1]%2 != s_l[i][j]:
            plus_j = 1
        else:
            plus_j = 0
        dp[i][j] = min(dp[i-1][j] + plus_i, dp[i][j-1] + plus_j)

#print(dp)
print((dp[h-1][w-1]+1)//2)

Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
  ll N,M;
  cin >> N >> M;
  ll a[M + 2] = {0};
  ll Mod = 1000000007;
  for (int i = 0; i < M; i++) {
    cin >> a[i + 1];
  }
  a[0] = -1;
  a[M+1] = N+1;
  ll f[120000] = {0};
  f[0] = 1;
  f[1] = 1;
  f[2] = 2;
  for (int i = 3; i < 114514; i++) {
    f[i] = (f[i - 1] + f[i - 2]) % Mod;
  }
  ll ans = 1;
  for (int i = 1; i < M+2; i++) {
    if (a[i] - a[i - 1] - 2 < 0) {
      ans = 0;
    } else {
    ans *= f[max((ll)(0),a[i] - a[i - 1] - 2)];
    ans %= Mod;
    }
  }
  cout << ans << endl;
  return 0;
}

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

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

int main() {
    int m, n;
    cin >> m >> n;
    cout << modpow(m, n, 1000000007) << endl;
}



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

using namespace std;

main() {
#ifdef HOME
    //freopen("input.txt", "r", stdin);
#endif // HOME
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin >> s;
    for (int j = 0; j < (int)s.size(); ++j) cout << "x";
    return 0;
}



Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int k, a, b,i;
	scanf("%d", &k);
	scanf("%d%d", &a, &b);
	if (b - a + 1 >= k)
	{
		printf("OK\n");
	}
	else
	{
		for (i = a;i <= b;i++)
		{
			if (i % k == 0)
			{
				printf("OK");
				break;
			}
		}
		if (i > b) printf("NG");
	}
	return 0;
}

Measured memory_bytes: 1728
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  vector<int> d(n);
  REP(i, n) cin >> d[i];
  ll sum = 0;
  REP(x, n) { FOR(y, x + 1, n) sum += (ll)d[x] * d[y]; }
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<functional>
#include<algorithm>
using namespace std;
int main(void)
{
	int n,a[10000],mx,i,j,cnt,p1,p2,x,cnt2,wk;
	while(1)	{
		scanf("%d",&n);
		if(n==0)	break;
		for(i=0;i<n;i++)	scanf("%d",&a[i]);
		mx=0;
		for(i=1;i<n;i++)	{
			if(a[i]!=a[i-1])	{
	//			printf("i=%d\n",i);
				wk=a[i];
				a[i]=a[i-1];
				p1=i-1;	p2=i;
				cnt2=0;
				while(1)	{
					cnt=0;
					x=p1;
					while(a[x]==a[p1])	{
						cnt++;
						p1--;
						if(p1<0)	break;
					}
					while(a[x]==a[p2])	{
						cnt++;
						p2++;
						if(p2>=n)	break;
					}
					if(cnt<4)	break;
					else cnt2+=cnt;
					if(p1<0 || p2>=n)	break;
				}
				a[i]=wk;
				mx=max(mx,cnt2);
				wk=a[i-1];
				a[i-1]=a[i];
				p1=i-1;	p2=i;
				cnt2=0;
				while(1)	{
					cnt=0;
					x=p1;
					while(a[x]==a[p1])	{
						cnt++;
						p1--;
						if(p1<0)	break;
					}
					while(a[x]==a[p2])	{
						cnt++;
						p2++;
						if(p2>=n)	break;
					}
					if(cnt<4)	break;
					else cnt2+=cnt;
					if(p1<0 || p2>=n)	break;
				}
				mx=max(mx,cnt2);	
				a[i-1]=wk;
			}		
		}
		printf("%d\n",n-mx);
	}
    return 0;
}


Measured memory_bytes: 1064
#include "bits/stdc++.h"
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <set>
#include <tuple>
using namespace std;

#define FOR(i,init,a) for(int i=init; i<a; i++)
#define rep(i,a) FOR(i,0,a)
#define rrep(i,a) for(int i=a; i>=0; i--)
#define rep1(i,a) for(int i=1; i<=a; i++)
#define cout1(a) cout << a << endl;
#define cout2(a,b) cout << a << " " << b << endl;
#define cout3(a,b,c) cout << a << " " << b << " " << c << endl;
#define cout4(a,b,c,d) cout << a << " " << b << " " << c << " " << d << endl;
#define mem(a,n) memset( a, n, sizeof(a))
#define all(a) a.begin(),a.end()
#define chmin(a,b) a=min(a,b);
#define chmax(a,b) a=max(a,b);

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LLINF = 1e18;
static const double pi = 3.141592653589793;

int N;
int nums[100009];

int up(int idx){
    int i=idx;
    for(;i+1<N;i++){
        if(nums[i]>nums[i+1]) break;
    }
    return i-idx+1;
}

int down(int idx){
    int i=idx;
    for(;i+1<N;i++){
        if(nums[i]<nums[i+1]) break;
    }
    return i-idx+1;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    cin>>N;
    rep(i,N) cin>>nums[i];
    
    int cnt=0,now=0;
    while(now<N){
        cnt++;
        now+=max(up(now),down(now));
    }
    cout1(cnt)
}

Measured memory_bytes: 640
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define fi first
#define se second
using namespace std;
template<class T> void rd(T &x) {
	x=0; int f=1,ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10-'0'+ch;ch=getchar();}
	x*=f;
}
template<class T> inline bool Cmin(T &x,T y) {return x>y?x=y,1:0;}
const int inf=1e9;
const int maxn=5000+5;
int n; char s[maxn],t[maxn];
vector< pair<int,int> > S,T;
int sol(int a,int b) {
	int an=0;
	while(S[a].fi!=n||T[b].fi!=n) an+=abs(S[a++].fi-T[b++].fi);
	return an;
}
void init(char *s,vector< pair<int,int> > &S) {
	for(int i=0;i<n;++i) S.push_back(make_pair(0,i&1));
	if((n&1)==(s[1]=='1')) S.push_back(make_pair(0,n&1));
	for(int i=1;i<n;++i) if(s[i]!=s[i+1]) {
		int c=S.back().se^1; 
		S.push_back(make_pair(i,c));
	}
	for(int i=0;i<2*n;++i) {
		int c=S.back().se^1;
		S.push_back(make_pair(n,c));
	}
}
int main() {
	rd(n);
	scanf("%s",s+1);
	scanf("%s",t+1);
	init(s,S),init(t,T);
	int an=inf;
	for(int i=0;i<=n;++i) if(S[i].se==T[n].se) Cmin(an,sol(i,n));
	for(int i=0;i<=n;++i) if(S[n].se==T[i].se) Cmin(an,sol(n,i));
	printf("%d\n",an);
	return 0;
}

Measured memory_bytes: 3956
#!/usr/bin/env python3
(h, w, m), *s = [[*map(int, i.split())] for i in open(0)]
r = [0] * (h + 1)
c = [0] * (w + 1)
for x, y in s:
    r[x] += 1
    c[y] += 1
R = max(r)
nr = {i for i, x in enumerate(r) if x == R}
C = max(c)
nc = {i for i, x in enumerate(c) if x == C}
count = sum(x in nr and y in nc for x, y in s)
print(R + C - (len(nr) * len(nc) == count))


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

#define LL long long
const int N = 1e5 + 5;
vector<pair<int,int>> g[N];
LL d[N]; int x, y, w;

void dfs(int v, int p) {
    for(auto u : g[v]) {
        if(u.first != p) {
            d[u.first] = d[v] + u.second;
            dfs(u.first, v);
        }
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    
    int n; cin >> n;
    for(int i = 0; i < n-1; i++) {
        cin >> x >> y >> w;
        g[x].emplace_back(y, w);
        g[y].emplace_back(x, w);
    }    

    dfs(1, 0);

    for(int i = 1; i <= n; i++) cout << d[i] % 2 << '\n';
}

Measured memory_bytes: 12712
#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>
#include <set>
#include <climits>

using namespace std;
#define debug(v) {cerr<<"\033[1;36m[debug]\033[m "<<#v<<" : "<<v<<endl;}
#define all(x) (x).begin(),(x).end()

using int64 = long long;


int main() {
    int k,s;
    cin >> k >> s;

    int ans = 0;
    for (int x=0; x<=k; x++) {
        for (int y=0; y<=k; y++) {
            int z = s - x - y;
            if (0 <= z && z <= k) ans++;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 760
N = int(input())
A = list(map(int, input().split()))

temp = [0]*N
for i in range(N-1,-1,-1):
  for j in [0,1]:
    temp[i] = j
    if sum(temp[i::i+1])%2 == A[i]:
      break
  else:
    print(-1)
    exit()
print(sum(temp)) 
anslist = []
for i in range(N):
  if temp[i] == 1:
    anslist.append(i+1)
if anslist == []:
  exit()
else:
  print(*anslist)
  exit()

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

using namespace std;

int main() {
  int A, B, C, X;
  cin >> A >> B >> C >> X;
  
  int ans = 0;
  
  for (int i = 0; i <= A; i++) {
    for (int j = 0; j <= B; j++) {
      if ((X - 500 * i - 100 * j) % 50 == 0 && 
          (X - 500 * i - 100 * j) / 50 <= C &&
          (X - 500 * i - 100 * j) / 50 >= 0) {
        ans++;
      }
    }
  }
  cout << ans << endl;

}

Measured memory_bytes: 256