akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include<vector>

#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = 1; i <= (n); i++)
#define drep(i,n) for(int i = (n)-1; i >= 0; i--)
#define srep(i,s,t) for (int i = s; i < t; i++)
#define rng(a) a.begin(),a.end()
using ll = long long;

using namespace std;



int main() {
    int n;
    cin>>n;
    vector<int>h(n);
    rep(i,n) cin>>h[i];
    for(int i = n-1; i > 0; i--) {
        if(h[i-1]-h[i]>1) {
            cout<<"No"<<endl;
            return 0;
        }
        else if(h[i-1]>h[i])
        {
            h[i-1]--;
        }
    }
    cout<<"Yes"<<endl;

    return 0;
}


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

// why am I so weak

const int MOD = 1e9 + 7;

int n;
int a[1055];

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

	for (int i = 0; i < n; i++) a[i] = i + 1;

	int res = 1;

	for (int i = 2; i <= n; i++) {
		int cnt = 1;

		for (int j = 0; j < n; j++) {
			while (a[j] % i == 0) {
				cnt++;
				a[j] /= i;
			}
		}
		
		res = (1ll * res * cnt) % MOD;
	}

	printf("%d\n", res);

	return 0;
}


Measured memory_bytes: 256
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    N,K,S = map(int,input().split())

    A = [str(S)] * K
    if S == 10 ** 9:
        T = S - 1
    else:
        T = S + 1

    for i in range(N-K):
        A.append(str(T))

    res = ' '.join(A)

    print(res)



main()


Measured memory_bytes: 13208
import Control.Applicative
import Data.List.Split (splitOn)

expand :: [String] -> String -> [String]
expand ans [] = ans
expand l (c:s) = expand (concatMap (\ss->[ ss++'+':[c], ss++[c] ]) l) s

eval s = sum $ map read $ splitOn "+" s

main = do
  (c:s) <- getLine :: IO String
  print $ sum $ map eval $ expand [[c]] s


Measured memory_bytes: 1020
#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 drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(x) (x).begin(),(x).end()
#define rrng(x) (x).rbegin(),(x).rend()
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define show(x) cout << #x << " = " << (x) << endl
#define show2(x,y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl
#define show3(x,y,z) cout << #x << " = " << (x) << ", " << #y << " = " << (y) <<  ", " << #z << " = " << (z) << endl
#define showv(v) rep(i,v.size()) printf("%d%c", v[i], i==v.size()-1?'\n':' ')
#define showv2(v) rep(j,v.size()) showv(v[j])
#define showt(t,n) rep(i,n) printf("%d%c", t[i], i==n-1?'\n':' ')
#define showt2(t,r,c) rep(j,r) showt(t[j],c)
#define showvp(p) rep(i,p.size()) printf("%d %d\n", p[i].first, p[i].second);
#define printv(v) rep(i,v.size()) printf("%d\n", v[i])
#define printt(t,n) rep(i,n) printf("%d\n", t[i])
#define incl(v,x) find(rng(v),x)!=v.end()
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define uni(x) x.erase(unique(rng(x)),x.end())
#define SP << " " <<
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
typedef vector<pii> vp;
typedef vector<tiii> vt;
const int mod = 1000000007;
const double EPS = 1e-9;
const int INF = (1<<30)-1;
const ll INFLL = (1LL<<62)-1;
#define dame { puts("No"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
inline int in() { int x; scanf("%d",&x); return x;}
//cout << fixed << setprecision(10);
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; }

ll dp[105][100500];

int main () {
  int N, W;
  cin >> N >> W;
  vi w(N), v(N);
  rep(i,N) cin >> w[i] >> v[i];

  rep(i,105)rep(j,100500) dp[i][j] = INFLL;
  dp[0][0] = 0;
  rep(i,N) {
    rep(j,100001) {
      chmin(dp[i+1][j], dp[i][j]);
      if (j-v[i] < 0 ) continue;
      chmin(dp[i+1][j], dp[i][j-v[i]]+w[i]);
    }
  }

  ll ans = 0;
  rep(i,100001) {
    if (dp[N][i] <= W) ans = i;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 82688
n = int(input())
s = input()

l = 0
p = 0
for i in range(n):
    if s[i]=='(':
        l+=1
    elif l>0:
        p+=1
        l-=1

a = s.count('(')
b = s.count(')')

print('('*(b-p)+s+')'*(a-p))

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

int main() {
    int n, k;
    cin >> n >> k;
    if (n%2 == 0 && n/2>=k) cout << "YES" << endl;
    else if (n%2 == 0 && n/2<k) cout << "NO" << endl;
    else if (n%2 == 1 && (n+1)/2>=k) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 256
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

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

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

use std::collections::HashSet;

fn g_dfs(g: &Vec<Vec<usize>>, h: &mut HashSet<usize>,
         path: (usize, usize), exclude: (usize, usize)) -> bool {
    if path.0 == path.1 {
        return true;
    }
    for x in &g[path.0] {
        if path.0 == exclude.0 && *x == exclude.1 {
            continue;
        }
        if h.contains(x) {
            continue;
        }
        h.insert(*x);
        if g_dfs(&g, h, (*x, path.1), exclude) {
            return true;
        }
    }
    return false;
}

fn main() {
    input! {
        n: usize,
        m: usize,
        ab: [(usize1,usize1);m]
    }
    let mut g = vec![Vec::new();n];
    for &(a,b) in &ab {
        g[a].push(b);
        g[b].push(a);
    }
    let mut res = 0;
    for &exclude in &ab {
        let mut reachable = true;
        for a in 0..n {
            for b in 0..n {
                let mut h = HashSet::new();
                if !g_dfs(&g, &mut h, (a,b), exclude) {
                    reachable = false;
                    break;
                }
            }
        }
        if reachable {
            res += 1;
        }
    }
    println!("{}", m - res);
}


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

typedef long long ll;
typedef long double ld;
#define pi 3.14159265359
#define inf 2147483647
#define INF 9223372036854775807
#define mod 1000000007
#define mod2 998244353

int main() {
    string S, T; cin >> S >> T;
    string ans = "Yes";
    int k = 0;
    while (S != T) {
        for (int i = 0; i < S.size() - 1; i++) {
            swap(S.at(i), S.at(i + 1));
        }
        k++;
        if (k == S.size()) {
            ans = "No";
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

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

vector<int> C;
int a,x;
vector<int> ans;
int S = 0;
void dfs(const Graph &G, int v, int p) {
    S += C[v];
    ans[v] += S;
    for (auto nv : G[v]) {
        if (nv == p) continue;
        dfs(G, nv, v);              
    }
    S -= C[v];
}
int main() {
    int N,Q; cin >> N >> Q;
    Graph G(N);
    for (int i=0;i<N-1;++i){
        int a,b; cin >> a >> b; --a;--b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    C.assign(N,0);
    ans.assign(N,0);
    for (int i=0;i<Q;i++){
        cin >> a >> x; --a;
        C[a] += x;
    }
    dfs(G,0,-1);
    for (int i=0;i<N;i++) {
        if (i) cout << " ";
        cout << ans[i];
    }
    cout << "\n";
    return 0;
}

Measured memory_bytes: 27392
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define cool ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int  long long int
#define pb push_back
#define fe first
#define lb lower_bound 
#define ub upper_bound
#define pii pair<pair<int,int>,pair<int,int> >
#define se second
#define endl "\n"
#define pi pair<int, int>
#define mi          map<int,int>
#define mii         map<pi,int>
#define vi vector<int> 
#define vvi vector<vi>
#define bs   binary_search
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rep1(i,a,b) for(int i=a;i<=b;i++)	
#define all(c) (c).begin(),(c).end()
#define sz(x)       (int)x.size() 
#define PI 3.14159265358979323846

 const int N=1e7+5;

 int mod= 1e9+7;
 int dx[4]={0,0,+1,-1};
 int dy[4]={+1,-1,0,0};  
 
 
int po(int a, int b) {
	a %= mod;
	int res = 1;
	while (b > 0) {
		if (b & 1)
			res = (res * a) % mod;
		a =(a*a) % mod;
		b >>= 1;
	}
	 return res;	
   }
  
int h,w,k,sum;
string s[10];

void solve() {
     cin>>h>>w>>k;
     rep(i,0,h) cin>>s[i];     
     
     for(int i=0;i<(1<<h);i++) {
		    for(int j=0;j<(1<<w);j++ ) {
				  int cnt=0;
				  for(int i1=0;i1<h;i1++) {
					     for(int j1=0;j1<w;j1++) {
							    if(!((1<<i1)&i) && !((1<<j1)&j) && s[i1][j1]=='#') cnt++;
							 }
					  }
					  if(cnt==k) sum++; 
				}
				
		 }
		 cout<<sum<<endl; 
   					   
 }

    
int32_t main() {
	cool;
	int t=1;	

	//cin>>t;
	while(t--)
	  solve();


return 0;	   
}


Measured memory_bytes: 3620
import numpy as np

def ABC107B(h, w, a):
    b = np.zeros((h, w), dtype=str)
    for i in range(h):
        b[i, :] = np.array(list(a[i]))
    H = []
    W = []
    for i in range(h):
        if any(b[i, :] == '#'):
            H.append(i)
    for j in range(w):
        if any(b[:, j] == '#'):
            W.append(j)
    lenH = len(H)
    lenW = len(W)
    for i in range(h):
        if H.count(i) == 1:
            string = ''
            for j in range(w):
                if W.count(j) == 1:
                    string = string + b[i, j]
            print(string)

h, w = map(int, input().split())
a = [0] * h
for i in range(h):
    a[i] = input()
ABC107B(h, w, a)


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

#define TIF(c,a,b) (c ? a : b)
#define FOR(i, m, n) for (ll i = m; i < ll(n); ++i)
#define READ(v) std::cin >> v;
#define WRITE(v) std::cout << v;
#define USORT(a,n) sort(a, a + n);
#define LSORT(a,n) sort(a, a + n, greater<int>());



#define cin std::cin
#define cout std::cout
using ll = long long;
using ull = unsigned long long;

int main()
{
	char* s = new char[100];
	cin >> s;
	int p = 0;
	bool y = true;
	while (s[p] != '\0')
	{
		if ((p + 1) % 2 == 0) 
        {
          if (!(s[p] == 'L' || s[p] == 'U' || s[p] == 'D')) y = false; 
        }
      	else
        {
        	if (!(s[p] == 'R' || s[p] == 'U' || s[p] == 'D')) y = false;
        }
		p++;
	}
	cout << TIF(y, "Yes", "No") << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
typedef long long ll;
int A[3][3], N;
bool punched[3][3];
bool ok[3][3];
int a[3][3],n;

int main() {
 ll n;
 cin >> n;
 ll h[n];
 rep(i,n) {
     cin >> h[i];
     }
 bool flag = true;

 rep(i,n-1){
     if(h[i]>h[i+1]) {
         h[i+1]++;
         if(h[i]>h[i+1]) flag = false;
     }
 }
 if(flag) cout << "Yes" << endl;
 else cout << "No" << endl;
 }


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>

using namespace std;

long long gcd(long long x, long long y) {
  while (y != 0) {
    long long tmp = x;
    x = y;
    y = tmp % y;
  }
  return x;
}

long long lcm(long long x, long long y) {
  return x / gcd(x, y) * y;
}

char s[100001];
char t[100001];

int main() {
  long long n, m;
  scanf("%lld %lld %s %s", &n, &m, s, t);
  long long x = lcm(n, m);
  long long y = lcm(x / n, x / m);
  for (long long i = 0; i < x; i += y) {
    if (s[i / (x / n)] != t[i / (x / m)]) {
      puts("-1");
      return 0;
    }
  }
  printf("%lld\n", x);
}



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

long long costb[5000][5000];
long long costw[5000][5000];
long long memo[5000][5000];

long long barr[2500];
long long warr[2500];

long long N;

int main(){
	cin >> N;
	for(long long i = 0; i < 2500; i++){
		barr[i] = -1;
		warr[i] = -1;
	}
	for(long long i = 0; i < 2 * N; i++){
		char c;
		long long a;
		cin >> c >> a;
		if(c == 'W'){
			warr[a] = i;
		}else{
			barr[a] = i;
		}
	}

	for(long long i = 0; i <= 2*N; i++){
		costb[i][N] = 0;
		//for(long long j = 1; j <= N; j++){
		for(long long j = N-1; j >= 0; j--){
			//cout << "i = " << i << endl;
			//cout << "barr[" << j + 1 << "] = " << barr[j+1] << endl;
			costb[i][j] = costb[i][j+1] + (barr[j+1] < i && barr[j+1] >= 0);
			//cout << "costb[" << i << "][" << j+1 << "] = " << costb[i][j+1] << endl;
			//cout << "costb[" << i << "][" << j << "] = " << costb[i][j] << endl;
		}
	}

	for(long long i = 0; i <= 2*N; i++){
		costw[i][N] = 0;
		for(long long j = N-1; j >= 0; j--){
			costw[i][j] = costw[i][j+1] + (warr[j+1] < i && warr[j+1] >= 0);
		}
	}


	for(long long i = 0; i <= 2*N; i++){
		for(long long j = 0; j <= 2*N; j++){
			memo[i][j] = INT_MAX;
		}
	}

	memo[0][0] = 0;
	for(long long i = 0; i <= N; i++){
		for(long long j = 0; j <= N; j++){
			//					      i+1のある場所より左にあるi+1より大きい黒 + i+1のある場所より左にあるjより大きい白
			if(i!=N){
			memo[i+1][j] = min(memo[i+1][j], memo[i][j] + costb[barr[i+1]][i+1] + costw[barr[i+1]][j]);
			}
			if(j!=N){
			memo[i][j+1] = min(memo[i][j+1], memo[i][j] + costw[warr[j+1]][j+1] + costb[warr[j+1]][i]);
			}
		}
	}

	cout << memo[N][N] << endl;
	/*
	for(long long i = 0; i <= N; i++){
		for(long long j = 0; j <= N; j++){
			cout << "memo[" << i << "][" << j << "]=" << memo[i][j] << endl;
		}
	}
	*/


}

Measured memory_bytes: 475136
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define str to_string
#define endl "\n"
#define PI 3.141592653589
using namespace std;
using lint = long long;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

//AC(*'ω'*)AC(*'ω'*)AC(*'ω'*)AC(*'ω'*)AC(*'ω'*)AC(*'ω'*)AC
int main(){
    string s;cin>>s;
    cout<<s.substr(0,4)<<" "<<s.substr(4)<<endl;
}


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

main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }

    if(arr[0]>1){
        arr[0]--;
    }
    for(int i=1;i<n;i++){
        if(arr[i]<arr[i-1]){
            cout<<"No";
            return 0;
        }

        if(arr[i]!=arr[i-1] and arr[i]>1){
            arr[i]--;
        }
    }
    
    cout<<"Yes";
    return 0;
}

Measured memory_bytes: 1024
// Undone
using System;
using System.Linq;
using System.Collections.Generic;
using System.Collections;
public class UnionFind {
  List<int> rank;
  List<int> list;

  public UnionFind(int n) {
    rank = Enumerable.Repeat(0, n).ToList<int>();
    list = Enumerable.Range(0, n).ToList<int>();
  }

  public int root(int x) {
    if (x != list[x]) {
      list[x] = root(list[x]);
    }
    return list[x];
  }

  public void unite(int x, int y) {
    x = root(x);
    y = root(y);
    if (rank[x] > rank[y]) {
      list[y] = x;
    } else {
      list[x] = y;
      if (rank[x] == rank[y]) {
        rank[y]++;
      }
    }
  }

  public bool same(int x, int y) {
    return (root(x) == root(y));
  }
}

public class Program {
  static void Main() {
    int n = ncin(), q = cin();
    UnionFind uf = new UnionFind(n);
    for (int i = 0; i < q; i++) {
      if (ncin() == 0) {
        uf.unite(cin(), cin());
      } else {
        bool same = uf.same(cin(), cin());
        int ans = (same) ? 1 : 0;
        Console.WriteLine(ans);
      }
    }
  }

  static List<int> _var;
  static int cin() { if (_var == null || _var.Count() == 0) { _var = ReadIntArray().ToList<int>(); } int ans = _var[0]; _var.RemoveAt(0); return ans; }
  static int ncin() { _var = ReadIntArray().ToList<int>(); return cin(); }
  static void Swap<T>(ref T a, ref T b) {T temp = a;a = b;b = temp;}
  static string ReadStr() { return Console.ReadLine(); }
  static int ReadInt() { return int.Parse(Console.ReadLine()); }
  static double ReadDouble() { return double.Parse(Console.ReadLine()); }
  static long ReadLong() { return long.Parse(Console.ReadLine()); }
  static char ReadChar() { return Console.ReadLine()[0]; }
  static string[] ReadStringArray() { return Console.ReadLine().Split(' '); }
  static int[] ReadIntArray() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
  static double[] ReadDoubleArray() { return Console.ReadLine().Split(' ').Select(double.Parse).ToArray(); }
  static long[] ReadLongArray() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
  static char[] ReadCharArray() { return Console.ReadLine().ToArray(); }
  static string[] ReadCharStringArray() { return Console.ReadLine().ToCharArray().Select(c => c.ToString()).ToArray(); }
}




Measured memory_bytes: 22572
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;

int main(){
  int n;cin >> n;
  vector<int> w(n);
  int sum=0;
  rep(i,n){
    cin >> w[i];
    sum += w[i];
  }
  int mn=1e+9;
  rep(i,n){
    if(i==0)continue;
    w[i]=w[i-1]+w[i];
    mn = min(mn,abs(sum-w[i]*2));
  }
  cout << mn;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long MOD = 1000000007;

void solve(long long N, long long K){
    ll ret = 0;
    for (ll i=K;i<=N+1;i++){
        ret += ((N + (N-i+1))*i/2 - (0 + i-1)*i/2 + 1) %MOD;
        ret %=MOD;
    }
    printf("%lld\n",(ret +MOD)%MOD);


}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    long long K;
    scanf("%lld",&K);
    solve(N, K);
    return 0;
}


Measured memory_bytes: 3816
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <utility>
#include <string>
#include <stack>
#include <regex>
#include <numeric>
#include <queue>
#include <set>

#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
const int MAX = 510000;
const int MOD = 1000000007;
using namespace std;

typedef long long ll;
long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit()
{
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < MAX; i++)
  {
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}

// 二項係数計算
long long COM(int n, int k)
{
  if (n < k)
    return 0;
  if (n < 0 || k < 0)
    return 0;
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
int main(int argc, char const *argv[])
{
  COMinit();
  ll n, k;
  cin >> n >> k;
  ll cnt = 0;
  vector<vector<ll>> f(k + 2, vector<ll>(k + 2));
  for (ll i = 2; i <= k; i++)
  {
    f[2][i] = (i - 1);
  }
  for (ll h = 3; h <= k + 1; h++)
  {
    for (ll j = 3; j <= min(h, n - h + 1); j++)
    {
      for (ll i = 1; i <= h - j + 1; i++)
      {
        f[j][h] += f[j - 1][h - i];
      }
      f[j][h] = f[j][h] % MOD;
    }
  }
  for (ll i = 1; i <= min(k, n - k + 1); i++)
  {
    if (i == 1)
    {
      cnt = COM(n - k + 1, i) % MOD;
    }
    else if (i == 2)
    {
      cnt = (COM(n - k + 1, i) * (k - 1)) % MOD;
    }
    else
    {
      cnt = (COM(n - k + 1, i) * f[i][k]) % MOD;
    }
    cout << cnt << endl;
  }
  if (n - k < k)
  {
    REP(i, 2 * k - n - 1)
    {
      cout << 0 << endl;
    }
  }

  return 0;
}


Measured memory_bytes: 43648
#!/usr/bin/env python3
import sys
INF = float("inf")


def main():
    H, W = map(int, input().split())
    C = [input() for _ in range(H)]
    for i in range(2*H):
        buf = []
        for j in range(W):
            buf.append(C[i//2][j])
        print("".join(buf))


if __name__ == '__main__':
    main()


Measured memory_bytes: 3316
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    res = n - k
    print(res if k != 1 else 0)


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long

const int maxn=2e5+5;

int n,k,a[maxn];

bool go(int t){
    int res=0;
    for(int i=0;i<n;i++){
        res+=(a[i]/t)-(a[i]%t==0);
    }
    return res<=k;
}


signed main(){
    IOS
    cin>>n>>k;
    for(int i=0;i<n;i++) cin>>a[i];
    int l=0,r=*max_element(a,a+n);

    while(l<r-1){
        int mid=(l+r)>>1;
        if(go(mid)) r=mid;
        else l=mid+1;
    }
    if(l and go(l)) r=l;
    cout<<r;
}

Measured memory_bytes: 5132
#include<bits/stdc++.h>
using namespace std;
using Graph=vector<vector<int>>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
typedef long long ll;

int main(){
    int H,W;cin>>H>>W;
    vector<string>S(H);
    rep(i,H){
        cin>>S.at(i);
    }
    Graph L(H,vector<int>(W));
    Graph R(H,vector<int>(W));
    Graph U(H,vector<int>(W));
    Graph D(H,vector<int>(W));
    rep(i,H){
        rep(j,W){
            if(j==0){
                L[i][j]=0;
                if(S[i][j]=='.'){
                    L[i][j]=1;
                }
            }
            else{
                if(S[i][j]=='#'){
                    L[i][j]=0;
                }
                else{
                    L[i][j]=L[i][j-1]+1;
                }
            }
        }
    }
    rep(i,H){
        for(int j=W-1;j>=0;j--){
            if(j==W-1){
                R[i][j]=0;
                if(S[i][j]=='.'){
                    R[i][j]=1;
                }
            }
            else{
                if(S[i][j]=='#'){
                    R[i][j]=0;
                }
                else{
                    R[i][j]=R[i][j+1]+1;
                }
            }
        }
    }
    rep(i,W){
        rep(j,H){
            if(j==0){
                U[j][i]=0;
                if(S[j][i]=='.'){
                    U[j][i]=1;
                }
            }
            else{
                if(S[j][i]=='#'){
                    U[j][i]=0;
                }
                else{
                    U[j][i]=U[j-1][i]+1;
                }
            }
        }
    }
    rep(i,W){
        for(int j=H-1;j>=0;j--){
            if(j==H-1){
                D[j][i]=0;
                if(S[j][i]=='.'){
                    D[j][i]=1;
                }
            }
            else{
                if(S[j][i]=='#'){
                    D[j][i]=0;
                }
                else{
                    D[j][i]=D[j+1][i]+1;
                }
            }
        }
    }
    priority_queue<int>Ans;
    rep(i,H){
        rep(j,W){
            Ans.push(L[i][j]+R[i][j]+U[i][j]+D[i][j]-3);
        }
    }
    cout<<Ans.top()<<endl;
}

Measured memory_bytes: 85748
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define cinf(n,x) for(int i=0;i<(n);i++)cin>>x[i];
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define ft first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define mod 1000000007
using namespace std;
using Graph = vector<vector<int>>;
typedef long long lint;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldouble;
typedef vector<int> vec;
typedef vector<ll> lvec;
typedef vector<ull> ulvec;
typedef vector<double> dvec;
typedef vector<pair<int,int>> pvec;
typedef vector<pair<ll,ll>> plvec;
typedef vector<tuple<ll,ll,ll>> tvec;
typedef vector<string> svec;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

int main(){
    int n,w,h;
    cin>>h>>w>>n;
    int m=max(h,w);
    if(n%m==0)cout<<n/m;
    else cout<<n/m+1;
}

Measured memory_bytes: 256
#include <cstdio>
#include <unordered_map>
#include <algorithm>
#include <map>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
const int N = 100001;
int a[N];
int n;
long long ans;
void work()
{
    long long v = 0;
    for (int i = 1; i <=  n / 2;  i ++)
        v += a[i] * 2;
    v += a[n / 2 + 1];
    v += a[n / 2 + 2];
    for (int i = n ; i > n / 2; i --)
        v -= a[i] * 2;
    ans = max(ans, abs(v));
}
bool cmp(const int x, const int y)
{
    return x > y;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1 ; i <= n ; i ++)
        scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);
    if (n & 1) {
        work();
        sort(a + 1, a + n + 1, cmp);
        work();
    } else{
       // sort(a + 1, a + n / 2 + 1, cmp);
        for (int i = 1; i < n / 2 ; i ++)
            ans += a[n - i + 1] + a[n - i] - 2 * a[i];
        ans += a[n] - a[n / 2];
    }
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long

const int N = 2e5 + 5;
int p = 1e9 + 7;

int32_t main()
{	
	IOS;
	int a[3];
	cin>>a[0]>>a[1]>>a[2];
	sort(a,a+3);
	for(int i=0;i<3;i++)
		if(a[i]%2==0)
		{
			cout<<"0";
			return 0;
		}
	cout<<a[0]*a[1];
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;

int N, arr[MAXN], carry[MAXN];
string str;

bool bisa(int len) {
    for (int i = 0; i < N; i++) {
        if ((arr[i]^carry[i]) == 1) {
            carry[i+1] ^= 1;
            if (i+len-1 >= N) {
                if (i >= len) return true;
                return false;
            }
            carry[i+len] ^= 1;
        }
        carry[i+1] ^= carry[i];
        carry[i] = 0;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    cin >> str;
    N = str.length();
    for (int i = 0; i < N; i++) arr[i] = str[i]-'0';
    
    int l = 0, r = str.length();
    while (l < r) {
        int m = (l+r+1)/2;
        memset(carry, 0, sizeof(carry));
        if (bisa(m)) l = m;
        else r = m-1;
    }
    cout << l << "\n";
    
    return 0;
}


Measured memory_bytes: 1232
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<functional>
#include<algorithm>
#include<stdlib.h>
#include<string>
#include<string.h>
#define _USE_MATH_DEFINES
#include<math.h>
#include<deque>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<iostream>
#include <bitset>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(auto i=a;i<b;i++)
#define all(_x) _x.begin(), _x.end()
#define r_sort(_x) sort(_x.begin(), _x.end(), std::greater<int>())
#define vec_cnt(_a, _n) (upper_bound(all(_a), _n) - lower_bound(all(_a), _n))
#define vec_unique(_a) _a.erase(std::unique(all(_a)), _a.end());
ll gcd(ll a, ll b) { return a % b == 0 ? b : gcd(b, a % b); }
//ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
#define INF 1 << 30
const int mod = 1000000007;
int main() {
	ll N;
	cin >> N;
	for (ll w = 1ll; w <= 3500; w++) {
		for (ll h = 1ll; h <= 3500; h++) {
			if (4 * w * h - N * (w + h) <= 0)continue;
			if (N * w * h % (4 * w * h - N * (w + h)) == 0) {
				printf("%lld %lld %lld\n", w, h, N * w * h / (4 * w * h - N * (w + h)));
				return 0;
			}
		}
	}
	return 0;
}


Measured memory_bytes: 256
// clang-format
#include <bits/stdc++.h>
#define rep(i, n) for (lli i = 0; i < (n); i++)
#define rrep(i, n) for (lli i = (n)-1; i >= 0; i--)
using namespace std;
using lli = long long int;

vector<lli> f(string s) {
  char c = '0';
  int u = 0;
  s.push_back('0');

  int n = s.size();
  vector<lli> ans;
  rep(i, n) {
    if (c == s[i]) {
    } else if (u) {
      ans.push_back(u);
      u = 0;
    }
    c = s[i];
    u++;
  }
  return ans;
}
void solve(std::string S, long long K) {
  char c = S[0];
  lli n = S.size();
  auto v = f(S);
  if (v.size() == 1) {
    cout << K * n / 2 << endl;
    return;
  }
  lli ans = 0;
//  for(auto s:v)cerr << s << endl;
  if (S.front() == S.back()) {
    for (int i = 1; i < v.size() - 1; i++) {
      ans += (v[i] / 2) * K;
    }
    ans += v[0] / 2 + v.back() / 2 + (K - 1) * ((v[0] + v.back()) / 2);
  } else {
    for (auto s : v)
      ans += (s / 2) * K;
  }
  cout << ans << endl;
}

int main() {
  std::string S;
  std::cin >> S;
  long long K;
  scanf("%lld", &K);
  solve(S, K);
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int

using namespace std;


int main(){

// #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,k;
cin>>n>>k;
vector<int>h(n);
for(int i=0;i<n;i++)
	cin>>h[i];
int dp[n+1] ;
dp[0] = INT_MAX;
dp[1] = 0;
for(int i=2;i<=n;i++){
	int tmp = INT_MAX;
	for(int j=1;j<i&&j<=k;j++)
		tmp = min(dp[i-j]+abs(h[i-1]-h[i-j-1]),tmp);
	dp[i]  =tmp;
}
cout<<dp[n];
}
		

Measured memory_bytes: 4008
package main

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

func exec(stdin *Stdin, stdout *Stdout) {
	n := stdin.ReadInt()
	s := stdin.Read()

	bits := map[string]*BIT{}
	for c := 'a'; c <= 'z'; c++ {
		bits[string(c)] = NewBIT(n)
	}

	chars := strings.Split(s, "")
	for i, c := range chars {
		bits[c].Add(i+1, 1)
	}

	q := stdin.ReadInt()
	for i := 0; i < q; i++ {
		query := stdin.ReadInt()
		if query == 1 {
			x := stdin.ReadInt()
			c := stdin.Read()
			if chars[x-1] != c {
				bits[chars[x-1]].Add(x, -1)
				chars[x-1] = c
				bits[chars[x-1]].Add(x, 1)
			}
		}

		if query == 2 {
			l := stdin.ReadInt()
			r := stdin.ReadInt()
			ans := 0
			for _, bit := range bits {
				d := bit.Sum(r) - bit.Sum(l-1)
				if d > 0 {
					ans++
				}
			}
			stdout.Println(ans)
		}
	}
}

func main() {
	stdout := NewStdout()
	defer stdout.Flush()
	exec(NewStdin(bufio.ScanWords), stdout)
}

type Stdin struct {
	stdin *bufio.Scanner
}

func NewStdin(split bufio.SplitFunc) *Stdin {
	s := Stdin{bufio.NewScanner(os.Stdin)}
	s.stdin.Split(split)
	s.stdin.Buffer(make([]byte, bufio.MaxScanTokenSize), int(math.MaxInt32))
	return &s
}

func (s *Stdin) Read() string {
	s.stdin.Scan()
	return s.stdin.Text()
}

func (s *Stdin) ReadInt() int {
	n, _ := strconv.Atoi(s.Read())
	return n
}

func (s *Stdin) ReadFloat64() float64 {
	n, _ := strconv.ParseFloat(s.Read(), 64)
	return n
}

type Stdout struct {
	stdout *bufio.Writer
}

func NewStdout() *Stdout {
	return &Stdout{bufio.NewWriter(os.Stdout)}
}

func (s *Stdout) Flush() {
	s.stdout.Flush()
}

func (s *Stdout) Println(a ...interface{}) {
	fmt.Fprintln(s.stdout, a...)
}

// Binary Indexed Tree (1 based indexed)
type BIT struct {
	size int
	tree []int
}

func NewBIT(size int) *BIT {
	bit := BIT{
		size: size,
		tree: make([]int, size+1),
	}
	return &bit
}

func (bit *BIT) Sum(i int) int {
	sum := 0
	for i > 0 {
		sum += bit.tree[i]
		i -= i & -i
	}
	return sum
}

func (bit *BIT) Add(i, x int) {
	for i <= bit.size {
		bit.tree[i] += x
		i += i & -i
	}
}


Measured memory_bytes: 116480
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<iostream>
using namespace std;


int main() {
	
	int w, h;



	while (true) {
		cin >> h >> w;
		if (h == 0 && w == 0)break;

		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (i == 0 || j == 0 || i == h - 1 || j == w - 1)printf("#");
				else printf(".");

			}
			printf("\n");
		}
		printf("\n");
	}


	//system("pause");
	return 0;
}


Measured memory_bytes: 3036
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<sstream>
using namespace std;
typedef  long long int lint;
typedef pair<int, int> P;
typedef pair<lint, lint> LLP;
typedef pair<char, char>CP;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define llower(v,hoge) *lower_bound(v.begin(), v.end(), hoge)
#define lupper(v,hoge) *upper_bound(v.begin(), v.end(), hoge)
/*
vector<char>al(26);
al = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
vector<char>AL(26);
AL = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
vector<char>NUM(10);
	NUM = { '0','1','2' ,'3' ,'4' ,'5' ,'6' ,'7' ,'8' ,'9' };
*/



int main() {
	int N;
	cin >> N;
	vector<int>H(N);
	rep(i, N) {
		cin >> H[i];
	}
	int ans = 1;
	int cnt = 0;
	for (int i = 1; i < N; i++) {
		for (int j = 0; j < i; j++) {
			if (H[j] > H[i]) {
				cnt++;
			}
		}
		if (cnt == 0) {
			ans++;
		}
		cnt = 0;
	}
	cout << ans << endl;
}

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

#define ll  long long
#define PII pair<ll,ll>
#define VI  vector<ll>
#define VB  vector<bool>
#define VC vector<char>
#define VVI vector<vector<ll>>
#define VVC vector<vector<char>>
#define VS  vector<string>
#define VP  vector<PII>
#define lf(i,a,b) for(ll i=a;i<=b;i++)
#define lr(i,a,b) for(ll i=a;i>=b;i--)
#define lfl(i,v) for(ll i=0;i<v.size();i++)
#define lrl(i,v) for(ll i=(ll)(v.size())-1;i>=0;i--)
#define chk2(a,b) cout<<"check :  "<<a<<" "<<b<<endl
#define chk3(a,b,c) cout<<"check :  "<<a<<" "<<b<<" "<<c<<endl
#define chk4(a,b,c,d) cout<<"check :  "<<a<<" "<<b<<" "<<c<<" "<<d<<endl
#define chk5(a,b,c,d,e) cout<<"check :  "<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<e<<endl
#define l_b(v,k)  lower_bound(v.begin(),v.end(),k)-v.begin()
#define u_b(v,k)  upper_bound(v.begin(),v.end(),k)-v.begin()
#define mod 1000000007
#define sort(v) sort(v.begin(),v.end())
#define p_b push_back
#define p_f push_front
#define m_p make_pair
#define fir first
#define sec second
#define sz size()
ll n,m,k,d;
string s;
ll dp[10005][105][2];
ll power(ll x,  ll y,  ll m) 
{   if (y == 0) 
        return 1; 
    ll p = power(x, y/2, m) % m; 
    p = (p * p) % m; 
    return (y%2 == 0)? p : (x * p) % m; 
} 



ll fun(ll ind,ll str,ll rem)
    {   if(ind>=n)
        {   if(rem%d==0)
                return 1;
            else
                return 0;
        }
        if(dp[ind][rem][str]!=-1)
            return dp[ind][rem][str];
        ll mx=str?s[ind]-'0':9;
        ll sum=0;
        lf(i,0,mx)
        {   ll remn=(i+rem)%d;
            if(i==mx)
            {   sum=(sum+fun(ind+1,str,remn))%mod;
            }
            else
            {   sum=(sum+fun(ind+1,0,remn))%mod;
            }
        }
        return dp[ind][rem][str]=sum;
    }
int main() 
{   cin>>s;
    cin>>d;
    n=s.length();
    memset(dp,-1,sizeof(dp));
    cout<<(fun(0,1,0)-1+mod)%mod<<endl;
}

Measured memory_bytes: 17408
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define ll long long
#define ull unsigned long long
#define ld long double
#define vl vector<long long>
#define vvl vector<vector<long long>>
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define rrep(i, x) for (ll i = ((ll)(x)-1); i >= 0; i--)
#define pll pair<long long,long long>
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define vvc vector<vector<char>>
#define vc vector<char>
#define vvb vector<vector<bool>>
#define vb vector<bool>
#define maxe(x) *max_element(all(x))
#define mine(x) *min_element(all(x))
#define Size(x) ((int)(x).size())
#define umap unordered_map
const long long INF = 1LL << 60;
const long double pi = 3.1415926535897932;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

    template<class T> inline bool chmin(T& a, T b) {
        if (a > b) {
            a = b;
            return true;
        }
        return false;
    }
    template<class T> inline bool chmax(T& a, T b) {
        if (a < b) {
            a = b;
            return true;
        }
        return false;
    }

//lis,modpow,uf,modncr,soinsubunkai,yakusurekkyo,gyakugen
//mint,dijkstra

    signed main(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        ll n;
        cin>>n;
        rep(i,n){
            ll a;
            cin>>a;
            if(a%2==1){
                cout<<"first"<<endl;
                return 0;
            }
        }
        cout<<"second"<<endl;
    }

Measured memory_bytes: 256
n,m,a,b = list(map(int,input().split()))
ban = [["."]*m for i in range(n)]
aa = a
bb = b
if n%2 == 1 and m %2 == 1 and n>=3 and m>=3 and a>=2 and b>=2:
    aa-=2
    bb-=2
    ban[-3][-3] = "<"
    ban[-3][-2] = ">"
    ban[-3][-1] = "^"
    ban[-2][-3] = "^"
    ban[-2][-1] = "v"
    ban[-1][-3] = "v"
    ban[-1][-2] = "<"
    ban[-1][-1] = ">"
    for i in range(0,m-m%2-2,2):
        if aa == 0:
            break
        ban[-1][i] = "<"
        ban[-1][i+1] = ">"
        aa-=1
    for i in range(0,n-n%2-2,2):
        if bb == 0:
            break
        ban[i][-1] = "^"
        ban[i+1][-1] = "v"
        bb-=1
    n-=1
    m-=1
    yo = aa//2
    ta = bb//2
    yoa = aa%2
    taa = bb%2
    if n*m//4 -1 < yo+ta+yoa+taa:
        n+=1
        m+=1
        ban = [["."]*m for i in range(n)]
    else:
        tu = []
        for i in range(0,n,2):
            for j in range(0,m,2):
                tu.append([i,j])
        tu.pop()
        for i in range(yo+ta):
            x,y = tu[i]
            if i<yo:
                ban[x][y] = "<"
                ban[x+1][y] = "<"
                ban[x][y+1] = ">"
                ban[x+1][y+1] = ">"
            else:
                ban[x][y] = "^"
                ban[x+1][y] = "v"
                ban[x][y+1] = "^"
                ban[x+1][y+1] = "v"            
        if yoa and taa:
            x,y = tu[yo+ta]
            ban[x][y] = "<"
            ban[x][y+1] = ">"
            x,y = tu[yo+ta+1]
            ban[x][y] = "^"
            ban[x+1][y] = "v"
        elif yoa:
            x,y = tu[yo+ta]
            ban[x][y] = "<"
            ban[x][y+1] = ">"
        elif taa:
            x,y = tu[yo+ta]
            ban[x][y] = "^"
            ban[x+1][y] = "v"  
        print("YES")
        for i in ban:
            print("".join(i))
        exit()

if n%2 ==1:
    for i in range(0,m-m%2,2):
        if a == 0:
            break
        ban[-1][i] = "<"
        ban[-1][i+1] = ">"
        a-=1
    n-=1
if m%2 == 1:
    for i in range(0,n,2):
        if b == 0:
            break
        ban[i][-1] = "^"
        ban[i+1][-1] = "v"
        b-=1
    m-=1
if n%2 == 0 and m%2 == 0:
    yo = a//2
    ta = b//2
    yoa = a%2
    taa = b%2
    if n*m//4 < yo+ta+yoa+taa:
        print("NO")
        exit()
    tu = []
    for i in range(0,n,2):
        for j in range(0,m,2):
            tu.append([i,j])
    for i in range(yo+ta):
        x,y = tu[i]
        if i<yo:
            ban[x][y] = "<"
            ban[x+1][y] = "<"
            ban[x][y+1] = ">"
            ban[x+1][y+1] = ">"
        else:
            ban[x][y] = "^"
            ban[x+1][y] = "v"
            ban[x][y+1] = "^"
            ban[x+1][y+1] = "v"            
    if yoa and taa:
        x,y = tu[yo+ta]
        ban[x][y] = "<"
        ban[x][y+1] = ">"
        x,y = tu[yo+ta+1]
        ban[x][y] = "^"
        ban[x+1][y] = "v"
    elif yoa:
        x,y = tu[yo+ta]
        ban[x][y] = "<"
        ban[x][y+1] = ">"
    elif taa:
        x,y = tu[yo+ta]
        ban[x][y] = "^"
        ban[x+1][y] = "v"                      
print("YES")
for i in ban:
    print("".join(i))

Measured memory_bytes: 79776
import bisect

X, Y, Z, K = list(map(int, input().split()))

x = sorted(list(map(int, input().split())), reverse=True)
y = sorted(list(map(int, input().split())), reverse=True)
z = sorted(list(map(int, input().split())), reverse=True)

x_i = 0
y_i = 0
z_i = 0

def cand_index(x_i, y_i, z_i):
    cs = [(x_i+1, y_i, z_i)] if x_i+1 < X else []
    cs += [(x_i, y_i+1, z_i)] if y_i+1 < Y else []
    cs += [(x_i, y_i, z_i+1)] if z_i+1 < Z else []
    return set(cs)

num_xyz = [[x[0]+ y[0]+ z[0], (0, 0, 0)]]
used = set()
ans = []
num = 0
for _ in range(K):
    num, xyz = num_xyz.pop(0)
    ans.append(num)

    new_cand = cand_index(*xyz)
    cand = new_cand - used
    used |= new_cand

    num_xyz += [[x[xyz[0]] + y[xyz[1]] + z[xyz[2]], xyz] for xyz in cand]
    num_xyz = sorted(num_xyz, key=lambda x: x[0], reverse=True)

for a in ans:
    print(a)


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

#define int long long
using ll = long long;
using ld = long double;
using intpair = pair<int, int>;
using intmap = map<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
const int MOD = 1e9 + 7;
inline int mod (ll a, int m = MOD) { return (a % m + m) % m; }
inline bool bit (ll b, ll i) { return b & (1 << i); }
inline ll ceiv (ll a, ll b) { return (a + b - 1) / b; }
//struct Fast {Fast(){cin.tie(0);ios::sync_with_stdio(0);}} fast;

#define debug(x) cerr << #x << ": " << x << '\n'
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()

signed main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << max({a*c, a*d, b*c, b*d}) << endl;
}

Measured memory_bytes: 3632
#[test]
fn test_solve() {
    assert_eq!(solve("9 3\n0001000100\n"), "1 3 2 3\n");
    assert_eq!(solve("5 4\n011110\n"), "-1\n");
    assert_eq!(solve("6 6\n0101010\n"), "6\n");
}
fn solve(src: &str) -> String {
    let mut sc = Scanner::from_str(src);
    let mut ret = String::new();
    use std::fmt::Write;
    
    let n: usize = sc.read();
    let m: usize = sc.read();
    let s: Vec<char> = sc.get().chars().collect();

    let mut dem = Vec::new();

    let mut pos = n;
    while pos > 0 {
        let mut dm = 0;
        for d in 1..m+1 {
            if pos < d {
                break;
            }
            if s[pos-d] == '0' {
                dm = std::cmp::max(dm, d);
            }
        }
        if dm == 0 {
            return "-1\n".to_string();
        }
        dem.push(dm);
        pos -= dm;
    }

    while let Some(d) = dem.pop() {
        write!(&mut ret, "{} ", d).unwrap();
    }

    ret.pop();
    ret.push('\n');
    
    ret
}
fn main() {
    let mut buf = String::new();
    use std::io::{Read, Write};
    std::io::stdin().read_to_string(&mut buf).unwrap();
    std::io::stdout().write_all(solve(&buf).as_bytes()).unwrap();
}
struct Scanner<'a>(std::str::SplitWhitespace<'a>);
impl<'a> Scanner<'a> {
    fn from_str(src: &str) -> Scanner {
        Scanner(src.split_whitespace())
    }
    fn get(&mut self) -> &str {
        self.0.next().unwrap()
    }
    fn read<T: std::str::FromStr>(&mut self) -> T {
        self.get().parse().ok().unwrap()
    }
}

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

int main(){
    int A, B;
    cin >> A >> B;

    int C = A + B;

    if(C % 2 == 0){
        cout << C / 2 << endl;
    }
    else{
        cout << "IMPOSSIBLE" << endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
     ll n;
     cin>>n;
     vector<pair<ll,ll>> ar[n+1];
     ll a,b,c;
     for(int x=0;x<n;x++)
        {
            cin>>a;
            for(int y=0;y<a;y++)
            {
                cin>>b>>c;
                ar[x].push_back({b,c});
            }
        }
        ll g=1<<n;
        ll ans=0;
        for(int x=0;x<g;x++)
        {
           bool k=true;
           for(int y=0;y<n;y++)
           {
               if(x&(1<<y))
               {
                   for(auto it : ar[y])
                   {
                       if(it.second==1)
                       {
                           if(!(x&(1<<(it.first-1))))
                            k=false;
                       }
                       else
                       {
                           if((x&(1<<(it.first-1))))
                            k=false;
                       }
                   }
               }
           }
           if(k)
           {
               ll d=x;
               ll f=0;
               while(d>0)
               {
                   if(d%2==1)
                    ++f;
                    d/=2;
               }
               ans=max(f,ans);
           }
        }
        cout<<ans;
}


Measured memory_bytes: 256
h1, m1, h2, m2, k = map(int, input().split())

if m1 <= m2:
    dh = h2 - h1
    dm = m2 - m1
else:
    dh = h2 - h1 -1
    dm = (60-m1) + m2

print(dh * 60 + dm - k)

Measured memory_bytes: 9176
#include <iostream>
#include <vector>
#include <algorithm>


int main()
{
    int n,q;
    std::cin>>n;
    std::vector<long long> a;

    for(int i = 0; i < n; i++)
    {
        int hoge;
        std::cin>>hoge;
        a.push_back(hoge);
    }

    std::cin>>q;

    for(int i = 0; i < q; i++)
    {
        int k;
        std::cin>>k;
        if (std::binary_search(a.begin(),a.end(), k))
        {
        std::cout <<'1'<< std::endl;
        }else
        {
        std::cout <<'0'<< std::endl;
        }
    }
    return 0;
}



Measured memory_bytes: 3944