akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define len(X) ((int)(X).size())

#ifdef __LOCAL
#define DBG(X) cout << #X << "=" << (X) << '\n';
#define SAY(X) cout << (X) << '\n';
#else
#define DBG(X)
#define SAY(X)
#endif

using namespace std;

using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int INT_INF = (int)(2e9);
const ll  LL_INF = (ll)(2e18);

const int NIL = -1;
static mt19937 _g(time(nullptr));

std::string pad(int num)
{
    char buffer[4];
    std::snprintf(buffer, sizeof(buffer), "%03d", num);
    return buffer;
}

inline ll randint(ll a, ll b) { ll w = (_g() << 31LL) ^ _g(); return a + w % (b - a + 1); }
inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T> inline T sign(T x) { return T(x > 0) - T(x < 0); }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline T fetch() { T ret; cin >> ret; return ret; }
template<typename T> inline vector<T> fetch_vec(int sz) { vector<T> ret(sz); for (auto& elem : ret) cin >> elem; return ret; }

#ifdef _MSC_VER
#  include <intrin.h>
#  define __builtin_popcount __popcnt
#endif

int solve()
{
    string str;

    std::cin >> str;

    if (str[2] == str[3] && str[4] == str[5])
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}

int main()
{
//    std::cout << solve() << std::endl;
    solve();

    return 0;
}

Measured memory_bytes: 256
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

H, W, A, B = list(map(int, sys.stdin.readline().split()))
if H % A == 0 and W % B == 0:
    print('No')
    exit()

print('Yes')
MAX = 998244353
ans = np.full((H, W), MAX // (A * B - 1), dtype=int)
if A > 1 and B > 1:
    ans[np.meshgrid(np.arange(A - 1, H, A), np.arange(B - 1, W, B))] = -MAX-1
elif A == 1:
    ans[:, np.arange(B - 1, W, B)] = -MAX-1
else:
    ans[np.arange(A - 1, H, A), :] = -MAX-1
print('\n'.join(map(lambda r: ' '.join(r), ans.astype(str))))


Measured memory_bytes: 40268
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a,b;
cin>>a>>b;
if((a+b)==3)
{printf("3\n");}
else if((a+b)==4)
{cout<<"2"<<endl;}
else if((a+b)==5)
{cout<<"1"<<endl;}

return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
//#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define bug1( x ) {cerr << (#x) <<"="<< x << endl;}
#define bug2( x , y ) {cerr << (#x) <<"="<< (x) << "    " << (#y) << "="<< (y) << endl;}
#define bug3( x , y , z ) {cerr << (#x) <<"="<<(x) << "    " << (#y) <<"="<< (y) << "    " << (#z) <<"="<< (z) << endl;}
#define bug4( x , y , z , w) {cerr << (#x) <<"="<<(x) << "    " << (#y) <<"="<< (y) << "    " << (#z) <<"="<< (z) << "    " << (#w) <<"="<< w << endl;}
#define bug5( x , y , z , w ,p) {cerr << (#x) <<"="<<(x) << "    " << (#y) <<"="<< (y) << "    " << (#z) <<"="<< (z) << "    " << (#w) <<"="<< w << "    " << (#p) <<"="<< p << endl;}
#define bug6( x , y , z , w ,p , q) {cerr << (#x) <<"="<<(x) << "    " << (#y) <<"="<< (y) << "    " << (#z) <<"="<< (z) << "    " << (#w) <<"="<< w << "    " << (#p) <<"="<< p << "    " << (#q) <<"="<< q << endl;}
#define bugn( x , n ) {cerr << (#x) <<":";for(int i=0;i<n;i++)cerr << x[i] <<"  "; cerr << endl;}
#define bugnm( x , n , m ) {cerr << (#x)<<endl;for(int i=0;i<n;i++){cerr << "Row #" << i<< ":";for(int j=0;j<m;j++)cerr << x[i][j] << "   ";cerr << endl;}}
typedef long long ll;
typedef long double ld;
using namespace std;

const int maxn = 2e5+10;
int msk[maxn],dp[maxn],n;
int mp[1<<26];
string s;
int32_t main(){
	IOS
	cin >> s;
	n = s.length();
	msk[0]=0;
	for(int i=1;i<=n;i++){
	   msk[i]=msk[i-1] ^ 1<<(s[i-1]-'a');
	}
	for(int i=0;i<1<<26;i++){
		mp[i]=1e8;
	}
	mp[0] = 0;
	for(int i=1;i<=n;i++){
		dp[i] = i;
		dp[i] = min( dp[i], mp[msk[i]] + 1);
		for(int j = 0 ; j < 26; j++ ){
			int cur = msk[i] ^ 1 << j;
			dp[i] = min( dp[i] , mp[cur] + 1);
		}
		if( mp[ msk[i] ] > dp[i] ){
			mp[ msk[i] ] = dp[i];
		}
	}
	cout << dp[n];
		
	
	
}
/*
 * long long or int?
 * index out of bound? 
 * Tested on own test case?corner?
 * Make more general solution.
 * Read Read Read Read ....
 */


Measured memory_bytes: 267492
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
/*
DPぽいがむずいな
1箇所生成して流す
2箇所生成して流す
3箇所生成して流す
とかのいずれ。
全探索？
流す回数で探索か？
どうせN回生成はする。
それぞれの箇所について、最小手を計算する？
5 100
100 16 39 199 2
100 16 39 139 2
作って流す、のコストと、その場で作る、と。
N*Nで間に合いそう
//それぞれの値について。
どこで生成したか、と
何回動かしたか。
違ったか。
一番コストの低いのが作ってまわす
2番目にコストも作ってまわす。
もしコストふえたらそこで終了？
そんなことないか
魔法回数固定して全探索
*/

int main(){
  ll N,x; cin>>N>>x;
  vector<ll> Z(N,0), minbox(N,1e9);
  for(int i=0; i<N; i++){
    ll a; cin>>a;
    Z[i]=a;
  }
  ll ans=1e14;
  for(int i=0; i<N; i++){//魔法回数
    for(int j=0; j<N; j++){
      ll pos=(N+j-i)%N;//生成ポジション
      minbox[j]=min(minbox[j], Z[pos]);
    }
    auto cost=accumulate(minbox.begin(), minbox.end(), 0LL) + i*x;
    ans=min(ans,cost);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
nim, mike = map(int, input().split())
A, B, C = map(int, input().split())
array = list(input())
sets = {'r':C, 's':A, 'p':B}

counter = 0

for i in range(nim):
    if i < mike:
        counter += sets[array[i]]
    else:
        if array[i] != array[i - mike]:
            counter += sets[array[i]]
        else:
            array[i] = 'z'

print(counter)


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

using ll=long long;
const ll MOD=1e9+7;

int H,W;
vector<string> graph;
int pjt[50][50];
queue<pair<int,int> > q;
const int dy[4]={0,0,1,-1};
const int dx[4]={1,-1,0,0};


int main(){
  cin >> H >> W;
  graph.resize(H);
  for(int i=0;i<W;i++){
    cin >> graph[i];
  }
  bool flag=true;

  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(graph[i][j]=='#'){
        bool flag2=false;
        for(int dir=0;dir<4;dir++){
          int ny=i+dy[dir];
          int nx=j+dx[dir];
          if(0<=ny&&ny<H&&0<=nx&&nx<W&&graph[ny][nx]=='#')
            flag2=true;
        }
        if (!flag2)
          flag=false;
      }
    }
  }    
  if (flag)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
      
  
}

Measured memory_bytes: 256
#include<iostream> 
#include<cstring> 
#include<algorithm> 
using namespace std;
string a,b;
int main()
{
    cin>>a;
	cin>>b;
    sort(a.begin(),a.end());
    sort(b.begin(),b.end(),greater<char>());
    if(a<b)
	{
		cout<<"Yes"<<endl;
	}
    else
	{
		cout<<"No"<<endl;
	 } 
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
 
using namespace std;
 
int main()
{
    int n,k;
    cin >> n >> k;
    int a[n];
    
    for(int i=0; i<n; i++) cin >> a[i];
    vector<int>dp(n+1,999999999);
 
    dp[0] = 0;
    dp[1] = abs(a[1]-a[0]);
    for(int i=2; i<n; i++){
        int jump = 0;
        for(int j=i-1; ; j--){
            if(jump==k) break;
            jump++;
            if(j<0) break;
            dp[i] = min(dp[i], dp[j]+abs(a[i]-a[j]));
        }
    }
    cout << dp[n-1];
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = (int)(a); i <= (int)(n); ++i)
#define rrep(i, a, n) for (int i = (int)(a); i >= (int)(n); --i)
#define debug(x) cerr << #x << " = " << x << "\n"
#define debugv(x) \
  rep(f, 0, (x.size() - 1)) cerr << x[f] << (f == (x.size() - 1) ? "\n" : " ")
#define debug2(x, y)                       \
  cerr << "(" << #x << "," << #y << ") = " \
       << "(" << x << "," << y << ")\n"
#define all(x) x.begin(), x.end()
#define each(a, x) for (auto& a : (x))
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define int long long
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
const int MX = 1e5 + 5, INF = 5LL << 57, MOD = 1e9 + 7;

int N, M;
string S;
vi va, vb;

void input() {
  ;
  cin >> N;
  va.resize(N);
  vb.resize(N);
  rep(i, 0, N - 1) { cin >> va[i]; }
  rep(i, 0, N - 1) { cin >> vb[i]; };
}
void solve() {
  vi vc = vi(N);
  rep(i, 0, N - 1) { vc[i] = i + 1; }
  int cnt = 0;
  int cnta, cntb;
  do {
    bool bb = true;
    bool ba = true;
    rep(i, 0, N - 1) {
      if (va[i] != vc[i]) {
        ba = false;
      }
      if (vb[i] != vc[i]) {
        bb = false;
      }
    }
    if (ba) {
      cnta = cnt;
    }
    if (bb) {
      cntb = cnt;
    }
    cnt++;
  } while (next_permutation(all(vc)));

  cout << abs(cntb - cnta) << endl;
}
signed main() {
  input();
  solve();
  return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"

#pragma warning(disable:4996)
using namespace std;


int main() {
	int N,K;cin>>N>>K;
	bool ok=N>K*2-2;
	if (ok) {
		cout<<"YES"<<endl;
	}
	else {
		cout<<"NO"<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main () {
  long N, M, A, B;
  cin >> N >> M;
  vector<pair<long, long>> data(N), D(M + 1);
  for(int i = 0; i < N; i++){
    cin >> A >> B;
    data.at(i).first = B;
    data.at(i).second = -A;
  }
  sort(data.begin(), data.end());
  reverse(data.begin(), data.end());
  long sub = 0, ans = 0;
  for(int i = 0; i < N; i++){
    for(int j = M + data.at(i).second; j >= sub; j--){
      if(D.at(j).first == 0){
        D.at(j).first = data.at(i).first;
        D.at(M + data.at(i).second).second = j;
        break;
      }
      if(D.at(j).second != 0)j = D.at(j).second;
      if(j == sub)sub = M + data.at(i).second;
    }
  }
  for(int i = 0; i < M + 1; i++)ans += D.at(i).first;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3328
#include<stdio.h>
#include<iostream>
#include<algorithm> // sort(ALL())
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue> // push(), front(), pop() 先入れ先出し
#include<map> // 連想配列 map<string, int>
#include<iomanip>
#include<set>
#include<utility>
using namespace std;
#define FOR(i, a, b) for(int i=(a); i<(b);  i++)
#define REP(i, n)    for(int i=0;   i<(n);  i++)
#define REP1(i, n)   for(int i=1;   i<=(n); i++)
#define pb push_back
#define mp make_pair
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define EPS 1e-7
#define ALL(obj) (obj).begin(), (obj).end()
#define MAX_INDEX(arg) distance(arg.begin(), max_element(arg.begin(), arg.end()))
using ul    = unsigned long;
using ll    = long long;
using ld    = long double;
using vint  = vector<int>;
using vll   = vector<ll>;
using pint  = pair<int, int>;
using pll   = pair<ll, ll>;
using vpint = vector<pint>;
using vpll  = vector<pll>;
const int INF = (int)1e9 + 1;
const int MOD = (int)1e9 + 7;
#define INT(argu) (int)(argu+EPS)

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

  int n;
  scan(n);
  n /= 2;
  vint a(100002), b(100002);
  int x, y;
  REP(i, n){
    cin >> x >> y;
    a[x]++; b[y]++;
  }

  vint::iterator itrmaxa = max_element(ALL(a));
  vint::iterator itrmaxb = max_element(ALL(b));
  bool find_2_a = find(next(itrmaxa), a.end(), *itrmaxa) != a.end();
  bool find_2_b = find(next(itrmaxb), b.end(), *itrmaxb) != b.end();
  if( !find_2_a && !find_2_b && (distance(a.begin(), itrmaxa) == distance(b.begin(), itrmaxb)) ){
    sort(ALL(a)); sort(ALL(b));
    cout <<
    n*2 -
    max(
      a[100000] + b.back(), a.back() + b[100000]
    )
    << endl;
  }else{
    cout << n*2 - *itrmaxa - *itrmaxb << endl;
  }

  return 0;
}


Measured memory_bytes: 1024
P=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101]
n=int(input())
A=[1]*n

for i in range(n):
	s=input()
	for j in range(10):
		A[i] *= P[ord(s[j])-97]

res=0
A.sort()
cnt=0

for i in range(n-1):
		if A[i]==A[i+1]:
			cnt += 1
		else:
			res += cnt*(cnt+1)//2
			cnt=0
if cnt != 0:
	res += cnt*(cnt+1)//2
print(res)

Measured memory_bytes: 8312
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <numeric>
using namespace std;
typedef long long int ll;

#define EPS (1e-7)
#define INF 1e18
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define PI (acos(-1))

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


int main() {

    ll N, M;
    cin >> N >> M;
    vector<ll> x(M), red(M - 1);
    REP(i, M) cin >> x[i];
    sort(x.begin(), x.end());
    REP(i, M - 1) red[i] = x[i + 1] - x[i];
    sort(red.begin(), red.end());
    //cout << "Hi" << endl;
    ll sum = 0;
    if (M > N) REP(i, M - N) sum += red[i];
    cout << sum << endl;

    return 0;
}

Measured memory_bytes: 1792
//
//  atcoder.cpp
//
//
///
#include <bits/stdc++.h>
#include <boost/optional.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/bimap/bimap.hpp>
#include <boost/bimap/multiset_of.hpp>
#include <boost/multi_array.hpp>
#include <boost/math/common_factor.hpp>
#include <boost/algorithm/string.hpp>

#define REP(i, N) for(int i=0; i<(N); i++)
#define REC(f, ...) (void)0; const auto f = [&](const auto f, __VA_ARGS__)
using namespace std;
using namespace boost::math;

using ll = long long;
namespace bst = boost;
template<typename T> class in {
    T value;
public:
    in() { cin >> value; }
    operator const T&() const { return value; }
    operator T&() { return value; }
    in& operator=(T source) { value = source; return *this; }
};
template<> class in<string> : public string {
public:
    in() { cin >> *this; }
};
template<class T> class inseq : public T {
public:
    template<typename... Arg> inseq(Arg... arg) : T(forward<Arg>(arg)...) { for (auto&& i : *this) cin >> i; }
};
template<class T> using invec = inseq<vector<T>>;

auto solve() {
  in<int> A, B;


  return (A >= 10 ? B : B + 100 * (10 - A));
}

template<typename T> void plot(const T& func) { cout << func() << endl; }
template<> void plot<void()>(void(&func)()) { func(); }
template<> void plot<double()>(double(&func)()) { cout << setprecision(9) << func() << endl; }

int main() {
  plot(solve);

  return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;
using ll = long long;
using ld = long double;

#define ALL(x) begin(x), end(x)
#define REP(i, n) for (size_t i = 0, i##_len = (n); i < i##_len; ++i)

void solve(string S) {
  int ans{};
  for (auto c: S) {
    if (c=='+') ++ans;
    else --ans;
  }
  cout << ans << endl;
}

int main() {
  string S;
  cin >> S;
  solve(S);
  return 0;
}


Measured memory_bytes: 256
N, K = map(int, input().split())
s = input()
L = 2 * K + 1
X = [0]*(2-int(s[0])) + [i+1 for i in range(N-1) if s[i]!=s[i+1]] + [N] * L
print(max([X[i+L]-X[i] for i in range(0, len(X)-L, 2)]))

Measured memory_bytes: 9356
N,M=list(map(int,input().split()))
ab= [list(map(int, input().split())) for i in range(M)]
ab=sorted(ab,key=lambda x:x[1])
cut=-1
ct=0
for a,b in ab:
    if a<=cut:
        continue
    else:
        cut=b-1
        ct+=1
print(ct)

Measured memory_bytes: 29848
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <cstring>
#include <tuple>
#include <vector>
#include <set>
#include <map>
#include <iterator>
#include <cmath>

using namespace std;
using lint = long long int;


int main() {
	int branch, expansionGoal;
	cin >> branch >> expansionGoal;

	double num = ((double)expansionGoal-1) / ((double)branch - 1);
	cout << (int)ceil(num);

	return 0;
}




Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<unordered_map>
#include<set>
#include<string>
#include<algorithm>
#include<math.h>
#include<numeric>
#include<iomanip>
#include<queue>
#include<functional>
#include<iso646.h>
#include<bitset>

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
typedef vector<long long> vll;
typedef pair<long long, long long> pll;

const double INF = 1e16;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;

ll const MAX_N = 1e5 + 10;
bool done[MAX_N];

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

vector<vll> E;
ll ans;

void func(ll f, ll u, ll p, ll K) {
	ans = (ans * (K - p)) % MOD;
	done[u] = true;

	p = 2;
	for (ll v : E[u]) {
		if (!done[v]) {
			func(u, v, p, K);
			p++;
		}
	}
}

int main() {
	ll i, j;
	ll r;
	cin >> r;
	ll ans = 3 * r * r;

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define chmax(x, y) { x = max(x, y); }

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> P(N); //順列の配列
    vector<int> C(N); //各マスに書かれた点数の配列
    for(int i = 0; i < N; i++){
        cin >> P.at(i);
    }
    for(int i = 0; i < N; i++){
        cin >> C.at(i);
    }
    for(int i = 0; i < N; i++){
        P.at(i)--; //1からstartだとめんどいのでデクリメント
    }
    long long ans = -1e18; //負の無限大
    for(int si = 0; si < N; si++){
        int x = si; //siをいじると壊れるので、xにsiを入れておく
        vector<int> score; //開始位置を決めると回り方が決まる。その周り方で通る各マスのスコア
        long long sum = 0; //配列scoreの合計値
        while(true){
            x = P.at(x); //位置を回していく
            score.push_back(C.at(x));
            sum += C.at(x);
            if(x == si){ //開始地点に戻ってきたらbreak
                break;
            }
        }
        int l = score.size(); //その周り方で何マス通るのか
        long long t = 0;
        for(int i = 0; i < l; i++){
            t += score.at(i);
            if(i + 1 > K){ //1周期の中でKを超えたとき、このbreakがないと壊れる
                break;
            }
            long long now = t;
            if(sum > 0){
                long long e = (K - (i + 1)) / l; //sumが正のとき、後ろに行けば行くほど高得点が取れる
                now += sum * e;
            }
            chmax(ans, now);
        }
    }
    /*for(int i = 0; i < N; i++){
        int score = 0;
        int blank = i;
        for(int j = 0; j < K; j++){
            score += C.at(P.at(blank) - 1);
            blank = P.at(blank) - 1;
        }
        cout << score << endl;
        if(score_max < score){
            score_max = score;
        }
    }*/
    cout << ans << endl;
}

Measured memory_bytes: 3696
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 300010;  // デフォルトでnの最大値は300000

// aのn乗を求める。計算量はO(logn)
ll modpow(ll a, ll n) {
    if(n == 0) {
        return 1;
    }
    if(n%2 == 1) {
        return (a * modpow(a, n-1))%mod;
    }
    return (modpow(a, n/2) * modpow(a, n/2))%mod;
}

ll inv(ll a) {
    return modpow(a, mod-2);
}

ll fact[MAX_N];
ll invfact[MAX_N];

// main関数でinit()を呼び出してからComb()を使用する
void init() {
    fact[0] = 1;
    invfact[0] = 1;
    for(ll i = 1; i < MAX_N; i++) {
        fact[i] = (i*fact[i-1])%mod;
        invfact[i] = inv(fact[i]);
    }
}
 
ll Comb(ll n, ll r) {
    if(r < 0 || n < 0 || n < r) {
        return 0;
    }
    ll res = fact[n];
    res = (res * invfact[r])%mod;
    res = (res * invfact[n-r])%mod;
    return res;
}
  
int main() {
    ll n, k;
    cin >> n >> k;
 
    init();
    
    exrep(i, 1, k) {
        ll ans = (Comb(n-k+1, i) * Comb(k-1, i-1))%mod;
        out(ans);
    }
    
    re0;
}

Measured memory_bytes: 4992
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define decimal(x) cout<<fixed<<setprecision(x)
#define fast ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
int n, dist[505][505];
bool seat[505][505];
int movex[]={0, 1, 0, -1};
int movey[]={1, 0, -1, 0};
void upd(int x, int y){
	int nw=dist[x][y];
	if(seat[x][y]) nw++;
	for(int move=0; move<4; move++){
		int nx=x+movex[move], ny=y+movey[move];
		if(dist[nx][ny]>nw){
			dist[nx][ny]=nw;
			upd(nx, ny);
		}
	}
}
int main(){ fast;
	cin>>n;
	for(int i=1; i<=n; i++) for(int j=1; j<=n; j++){
		seat[i][j]=true;
		dist[i][j]=min(min(i, n+1-i), min(j, n+1-j))-1;
	}
	int rs=0;
	for(int i=0; i<n*n; i++){
		int nw; cin>>nw;
		int x=(nw+n-1)/n, y=nw%n;
		if(y==0) y=n;
		rs+=dist[x][y];
		seat[x][y]=false;
		upd(x, y);
	}
	cout<<rs<<endl;
}

Measured memory_bytes: 20284
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;

typedef long long ll;
#define rep(i, n) for(int i = 0; i < n; i++)

int main(){
    int R, G, B, N;
    cin >> R >> G >> B >> N;
    ll cnt = 0;
    rep(r, N+1){
        rep(g, N+1){
            ll sub = N - r * R - g * G;
            if(sub >= 0 && sub % B == 0) cnt++; 
        } 
    }
    cout << cnt << endl;
    return 0;
}

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

int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i=0; i<N; i++){
    cin >> A[i];
  }
  vector<int> Color(N);
  for (int i=0; i<N; i++){
    Color[i] = -1;
  }
  int cnt = 0;
  for (int i=N-1; i>=0; i--){
    if (i == N-1){
      Color[cnt] = A[i];
      cnt++;
    } else{
      // Color の中で最大なのは常に Color[cnt-1]
      // A[i] がどのColor よりも大きかったら(同じ値でも)
      if (A[i] >= Color[cnt-1]){
        Color[cnt] = A[i];
        cnt++;
      } else{
        // A[i]より大きい最小のColor を A[i]と置き換える そうするとColor の大小関係が変わらない
        for (int j=0; j<cnt; j++){
          if (A[i] < Color[j]){
            Color[j] = A[i];
            break;
          }
        }
      }
    }
  }

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


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

using namespace std;

const int NMAX = 2000 + 5;

int n, k;
int h[NMAX];
int sz[NMAX];

int dp[NMAX][NMAX]; //dp[node][h] = numarul minim de noduri care trebuie
                    //eliminate pentru a obtine inaltimea maxim h in
                    //subarborele lui node

int dp2[NMAX][NMAX]; //dp[son][h] = numarul minim de noduri care trebuie
                     //eliminate dintre nodurile de pana la fiul son      
                     //(exclusiv) astfel incat inaltimea maxima sa fie h,
                     //iar diametrul sa nu depaseasca k

vector <int> graph[NMAX];

void upd(int &where, int val) {
    if (val < where)
        where = val;
}

void dfs(int node, int father) {
    if (father)
        graph[node].erase(find(graph[node].begin(), graph[node].end(), father));
    
    h[node] = 0;
    sz[node] = 1;
    for (auto it: graph[node]) {
        dfs(it, node);
        if (h[it] > h[node])
            h[node] = h[it];
        sz[node] += sz[it];
    }

    ++ h[node];

    int max_h = 0;
    for (int son = 0; son < static_cast <int>(graph[node].size()); ++ son) {
        for (int j = 0; j <= max(max_h, h[graph[node][son]]) && j <= k; ++ j)
            dp2[son + 1][j] = NMAX;

        for (int j = 0; j <= max_h && j <= k + 1; ++ j) {
            for (int l = 0; l <= h[graph[node][son]]; ++ l) {
                if (j + l <= k)
                    upd(dp2[son + 1][max(j, l)], dp[graph[node][son]][l] + dp2[son][j]);
            }
        }

        max_h = max(max_h, h[graph[node][son]]);
    }
    
    dp[node][0] = sz[node];
    for (int j = 0; j < h[node] && j <= k; ++ j)
        dp[node][j + 1] = dp2[graph[node].size()][j];
}

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

    int a, b;
    for (int i = 1; i < n; ++ i) {
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    dfs(1, 0);

    int ans = NMAX;

    for (int root = 1; root <= n; ++ root) {
        int current = NMAX;
        
        for (int l = 0; l <= k + 1 && l <= h[root]; ++ l)
            upd(current, dp[root][l]);
        upd(ans, n - sz[root] + current);
    }

    cout << ans << '\n';

    return 0;
}

Measured memory_bytes: 16384
#include <stdio.h>
#include <iostream>
#include <stack>

using namespace std;

#define max(a,b)(a>b?a:b)

struct POINT{
	int x;
	int y;
	int c;
	POINT(int X,int Y,int C){
		x = X;y = Y;c=C;
	}
};

stack<POINT> st;

int h,w,c;
int panel[8][8][2]={0};
int ans=0;



void show(int ans){
	cout << "--- panel contents"<<endl;
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			cout << panel[i][j][0] << " ";
		}
		cout << endl;
	}
	cout<< "--- count = "<< ans<< endl<<endl;
}

void change(int c){
	for(int i=0;i<h;i++)
		for(int j=0;j<w;j++)
			if(panel[i][j][1])
				panel[i][j][0]=c;
}

int countPanel(){
	int count=0;
	for(int i=0;i<h;i++)
		for(int j=0;j<w;j++)
			if(panel[i][j][1])
				count++;
	return count;
}

void push(POINT pt,int dp){
	panel[pt.y][pt.x][1]=dp;
	if(pt.x>0&&panel[pt.y][pt.x-1][1]!=dp&&panel[pt.y][pt.x-1][0]==pt.c){
		st.push(POINT(pt.x-1,pt.y,panel[pt.y][pt.x-1][0]));
	}
	if(pt.x<w-1&&panel[pt.y][pt.x+1][1]!=dp&&panel[pt.y][pt.x+1][0]==pt.c){
		st.push(POINT(pt.x+1,pt.y,panel[pt.y][pt.x+1][0]));
	}
	if(pt.y>0&&panel[pt.y-1][pt.x][1]!=dp&&panel[pt.y-1][pt.x][0]==pt.c){
		st.push(POINT(pt.x,pt.y-1,panel[pt.y-1][pt.x][0]));
	}
	if(pt.y<h-1&&panel[pt.y+1][pt.x][1]!=dp&&panel[pt.y+1][pt.x][0]==pt.c){
		st.push(POINT(pt.x,pt.y+1,panel[pt.y+1][pt.x][0]));
	}
	if(!st.empty()){
		POINT t_st=st.top();
		st.pop();
		push(t_st,dp);
	}
}


void depth(int dp){

	if(dp==5){
		push(POINT(0,0,panel[0][0][0]),dp+1);
		ans=max(ans,countPanel());
	}
	else{
		//状態を保存
		int tmp[8][8][2]={0};
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				tmp[i][j][0]=panel[i][j][0];
				tmp[i][j][1]=panel[i][j][1];
			}
		}

		if(dp==4){
			//同色を結合
			push(POINT(0,0,panel[0][0][0]),dp+1);
			change(c);
			//再帰
			depth(dp+1);
			//状態を戻す
			for(int i=0;i<h;i++){
				for(int j=0;j<w;j++){
					panel[i][j][0]=tmp[i][j][0];
					panel[i][j][1]=tmp[i][j][1];
				}
			}
		}else{
			//全色色を変えていく
			for(int i=1;i<=6;i++){
				//同色を結合
				push(POINT(0,0,panel[0][0][0]),dp+1);
				change(i);
				//再帰
				depth(dp+1);
				//状態を戻す
				for(int i=0;i<h;i++){
					for(int j=0;j<w;j++){
						panel[i][j][0]=tmp[i][j][0];
						panel[i][j][1]=tmp[i][j][1];
					}
				}
			}
		}

	}
}

int main(void){

	while(1){

		ans=0;
		cin >> h>>w>>c;

		if(!h&&!w&&!c)
			break;

		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				cin >> panel[i][j][0];
			}
		}

		depth(0);

		cout << ans <<endl;

	}

	return 0;
}

Measured memory_bytes: 1220
#include<iostream>
using namespace std;
int main(){

	for(int i=0; i<3; i++){
		int hs,ms,ss,hf,mf,sf;
		cin >> hs >> ms >> ss >> hf >> mf >> sf;

		int S,F,Th,Tm,Ts;

		S = 3600*hs+60*ms+ss;
		F = 3600*hf+60*mf+sf;

		Ts = (F-S)%60;
		Tm = ((F-S-Ts)%3600)/60;
		Th = (F-S-Ts-Tm)/3600;

		cout << Th << " " << Tm << " " << Ts << endl;

	}

	return 0;
}


Measured memory_bytes: 3076
#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int A,B,C,D;
    cin >> A >> B >> C >> D;
    int Takahashi = C/B;
    int Aoki = A/D;
    if (C%B != 0)
    {
        Takahashi++;
    }
    if (A%D != 0)
    {
        Aoki++;
    }
    if (Takahashi <= Aoki)
    {
        cout << "Yes";
    }else{
        cout << "No";
    }
}

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

int main()
{
	int A,B,C;
	cin >> A >> B >> C;
	cout << min(B/A,C) << endl;
	return 0;
}

Measured memory_bytes: 256
//         Jai Saraswati Maa       Om Namah Shivaay        Jai Bhawani
// You have to work hard and keep coding till you get correct output never quit! :-)
// May the force be with you
// Ganpatai Bappa Morya! Mangal Murti Morya!
#include<bits/stdc++.h>
#define sc(x) scanf("%d",&x);
#define scc(x,y) scanf(" %d %d",&x,&y);
#define sccc(x,y,z) scanf("%d %d %d",&x,&y,&z);
#define sl(x) scanf("%lld",&x);
#define sll(x,y) scanf("%lld %lld",&x,&y);
#define slll(x,y,z) scanf("%lld %lld %lld",&x,&y,&z);
#define pf(x) printf("%d",x);
#define pfn(x) printf("%d\n",x);
#define pl(x) printf("%lld",x);
#define pln(x) printf("%lld\n",x);
#define st(s) scanf("%s",s);
using namespace std;
int main()
{
    int n,i,j,p,l,k,c;
    sc(n)
    char s[n][15];
    for(i=0;i<n;i++)
    {
        scanf("%s",s[i]);
    }
    for(i=1;i<n;i++)
    {
        p=strlen(s[i-1]);
        if(s[i][0]!=s[i-1][p-1])
        {
            printf("No\n");
            return 0;
        }
        for(j=0;j<i;j++)
        {
            l=strlen(s[j]);c=0;
            if((strlen(s[i]))==l)
            {
                for(k=0;k<l;k++)
                {
                    if(s[i][k]==s[j][k])
                    {
                        c++;
                    }
                }
              if(c==l)
              {
                  printf("No\n");
                  return 0;
              }
            }
        }
    }
    printf("Yes\n");
 return 0;
}


Measured memory_bytes: 256
import sys
import heapq
import re
from heapq import heapify, heappop, heappush
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# ここから書き始める
def dfs(n, i, a_total, b_total, c_total, a_cnt, b_cnt, c_cnt):
    if i == n:
        global ans
        if a_cnt == 0 or b_cnt == 0 or c_cnt == 0:
            return
        a_cost = abs(a - a_total) + max(0, (a_cnt - 1) * 10)
        b_cost = abs(b - b_total) + max(0, (b_cnt - 1) * 10)
        c_cost = abs(c - c_total) + max(0, (c_cnt - 1) * 10)
        cost = a_cost + b_cost + c_cost
        if ans > cost:
            ans = cost
        return
    dfs(n, i + 1, a_total + l[i], b_total, c_total, a_cnt + 1, b_cnt, c_cnt)
    dfs(n, i + 1, a_total, b_total + l[i], c_total, a_cnt, b_cnt + 1, c_cnt)
    dfs(n, i + 1, a_total, b_total, c_total + l[i], a_cnt, b_cnt, c_cnt + 1)
    dfs(n, i + 1, a_total, b_total, c_total, a_cnt, b_cnt, c_cnt)

n, a, b, c = map(int, input().split())
l = [int(input()) for i in range(n)]
ans = INF
dfs(n, 0, 0, 0, 0, 0, 0, 0)
print(ans)

Measured memory_bytes: 75864
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ for(auto it : P) { s << "<" << it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ for(auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s << endl; }


int main() {
    int A, B;
    while (cin >> A >> B) {
        long long res = -1;
        for (int i = 1; i <= 1000000; ++i) {
            int a = i*8/100;
            int b = i*10/100;
            if (a == A && b == B) {
                res = i;
                break;
            }
        }
        cout << res << endl;
    }

}


















Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cmath>


using ull = unsigned long long;

int main() {

	ull n;
	std::cin >> n;

	if (n == 1) {
		std::cout << "Yes\n2\n1 1\n1 1\n";
		return 0;
	}


	ull ss{};
	for (ull i{2}; i < 2 * n; ++i) {
	//	std::cout << i << " ";
		if (i*(i - 1)/2 == n) {
			ss = i;//subset size
		}
	}

	//std::cout <<"ss "<< ss<<"\n";

	if (ss == 0) {
		std::cout << "No\n";
		return 0;
	}

	std::vector<std::vector<int>> v;
	v.resize(ss);
	//for (auto&e : v) {
	//	e.resize(ss - 1);
	//}
	//for (const auto&e : v)
	//	std::cout <<"S "<< e.size() << "\n";


	int c{1};
	for (int i{}; i < ss; ++i) {
		for (int j{ i + 1 }; j < ss; ++j) {
		//	std::cout <<c<<" "<< i << "*" << j << " -> " << i+j-1<<" ";
			v[i].emplace_back( c );
			v[j].emplace_back( c );
			++c;
		}//std::cout << "\n";
	}

	std::cout << "Yes\n";
	std::cout << v.size() << "\n";
	for (const auto&e : v) {
		auto s = e.size();
		std::cout << s << " ";

		std::cout << e[0];
		for (ull i{1}; i < s; ++i) {
			std::cout << " " << e[i];
		}std::cout << "\n";
	}


	return 0;
}

Measured memory_bytes: 2304
#include <algorithm>
#include <cmath>
#include <complex>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <ios>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <vector>
#define itn int
#define retrun return
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
using namespace std;
typedef long long llong;
typedef pair<int, int> pii;
llong gcd(llong a, llong b) {
	if (a < b) std::swap(a, b);
	if (a % b == 0)
		return b;
	else
		return gcd(b, a % b);
}
llong lcm(llong a, llong b) {
	llong g = gcd(a, b);
	return a * b / g;
}
//ここまで共通
int K, N;
vector<int> A;
int main() {
	cin >> K >> N;
	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		A.push_back(a);
	}
	int ANS = K;
	for (int i = 0; i < N; i++) {
		if (i == 0) {
			int tmp = A[N - 1] - A[i];
			tmp = max(tmp, K - tmp);
			ANS = min(tmp, ANS);
		}
		else {
			int tmp = A[i] - A[i - 1];
			tmp = max(tmp, K - tmp);
			ANS = min(tmp, ANS);
		}
	}
	cout << ANS << endl;
	return 0;
}

Measured memory_bytes: 1400
#include <cstdio>

int c[35];
int n, m;

int main() {
    int i, x, k;
    int ans = 0;

    scanf("%d %d", &n, &m);
    for (i = 1; i <= n; i++) {
        scanf("%d", &k);
        while (k) {
            scanf("%d", &x);
            c[x]++;
            k--;
        }
    }
    for (i = 1; i <= m; i++)
        ans += c[i] == n;
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 128
N = gets.to_i
es = {}
(N-1).times{
  u,v,w = gets.split.map &:to_i
  es[u] ||= {}; es[v] ||= {}
  es[u][v] = es[v][u] = w
}

colors = Array.new(N+1,nil)
colors[1] = 0
ns = [1]
while ns.size > 0 do
  xs = []
  ns.each{ |u|
    next if !es[u]
    es[u].each{ |v,w|
      es[v].delete(u)
      colors[v] = colors[u] ^ (w % 2)
      xs << v
    }
  }
  ns = xs
end

puts colors[1..-1]

Measured memory_bytes: 39164
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <queue>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <stdio.h>
#include <complex>
#include <cstdint>
#include <tuple>

#define M_PI       3.14159265358979323846

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<int, PII> TIII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;

//container util

//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)
#define MOD 998244353

int dp[100005];
int dx[] = { 1,6,36,216,1296, 7776, 46656, 9,81,729,6561,59049 };

int main() {
	int n;
	scanf("%d", &n);
	memset(dp, 0x7f, sizeof(dp));
	dp[0] = 0;
	REP(i, n) REP(j, 12) if (i + dx[j] <= n)dp[i + dx[j]] = min(dp[i + dx[j]], dp[i] + 1);
	printf("%d\n", dp[n]);
	return 0;
}

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


def readstr():
    return input().strip()


def readint():
    return int(input())


def readnums():
    return map(int, input().split())


def readstrs():
    return input().split()


def main():
    X, K, D = readnums()
    if X <= 0:
        X = -X
    if X // D >= K:
        print(X - K * D)
    else:
        a1 = X % D
        a2 = D - X % D
        if (K - X // D) % 2:
            print(a2)
        else:
            print(a1)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9216
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <cmath>
#include <complex> // complex<double> a(1.2 , 2.3);// real(): 1.2, imag()2.3
using namespace std;

#define MOD 1000000007
#define ll long long
#define ld long double
#define FOR(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rmsame(a) sort(all(a)),a.erase(unique(all(a)), a.end())
#define rmvector(a,b) rep(i,a.size())rep(j,b.size())if(a[i]==b[j]){a.erase(a.begin()+i);i--;break;}
template<typename X> bool exist(vector<X> vec, X item){return find(all(vec), item)!=vec.end();}

ll L[90] = {2,1};

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


  ll N ;cin >> N;
  for(ll i = 2;i<=N;i++){
    L[i]=L[i-1]+L[i-2];
  }

  cout << L[N] << endl;
  //cout << fixed << setprecision(16) << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

template <class T>
void chmax(T& lhs, const T& rhs){
  if(lhs >= rhs) return;
  lhs = rhs;
}
template <class T>
void chmin(T& lhs, const T& rhs){
  if(lhs <= rhs) return;
  lhs = rhs;
}


struct MaxThree {
  priority_queue<int> que;

  void add(int x){
    que.push(x);
  }

  ll get(){
    int a = 0, b = 0, c = 0;
    if(!que.empty()){
      a = que.top(); que.pop();
    }
    if(!que.empty()){
      b = que.top(); que.pop();
    }
    if(!que.empty()){
      c = que.top(); que.pop();
    }
    ll ret = (ll)a + (ll)b + (ll)c;
    que.push(a);
    que.push(b);
    que.push(c);
    return ret;
  }
};


int R, C, K;
int field[3005][3005];

ll dp[3005][3005];


int main(){
  cin >> R >> C >> K;
  rep(i,K){
    int r, c, v;
    cin >> r >> c >> v;
    r--;
    c--;
    field[r][c] = v;
  }

  {
    MaxThree maxthree;
    for(int j=C-1; j>=0; j--){
      maxthree.add(field[R-1][j]);
      dp[R-1][j] = maxthree.get();
    }
  }
  
  for(int i=R-2; i>=0; i--){
    vector<vector<ll>> dp2(4, vector<ll>(C+10, -1));

    dp2[0][C-1] = dp[i+1][C-1];
    dp2[1][C-1] = field[i][C-1] + dp[i+1][C-1];
    for(int j=C-2; j>=0; j--){
      dp2[0][j] = dp[i+1][j];
      dp2[1][j] = field[i][j] + dp[i+1][j];

      rep(jj,4){
        chmax(dp2[jj][j], dp2[jj][j+1]);
      }
      REP(jj,1,4){
        chmax(dp2[jj][j], field[i][j] + dp2[jj-1][j+1]);
      }
    }
    
    rep(j,C){
      rep(jj,4){
        dp[i][j] = max(dp[i][j], dp2[jj][j]);
      }
    }
  }

  cout << dp[0][0] << endl;

  
  return 0;
}


Measured memory_bytes: 109196
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define dbg(x) cout<<#x<<":"<<x<<endl
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;

int main(){
  ll n,p=1e9+7;
  cin>>n;
  n--;
  
  ll dp[101][4][4][4]={};
  for(int j=0;j<4;j++)
    for(int k=0;k<4;k++)
	 for(int l=0;l<4;l++){
	   if(j==0&&k==1&&l==2)continue;
	   if(j==1&&k==0&&l==2)continue;
	   if(j==0&&k==2&&l==1)continue;
	   dp[2][j][k][l]=1;
	 }
  
  for(int i=2;i<n;i++){
    for(int j=0;j<4;j++){
	 for(int k=0;k<4;k++){
	   for(int l=0;l<4;l++){
		dp[i+1][k][l][0]+=dp[i][j][k][l];
		dp[i+1][k][l][0]%=p;
		dp[i+1][k][l][3]+=dp[i][j][k][l];
		dp[i+1][k][l][3]%=p;

		if(k!=0||l!=2){
		  dp[i+1][k][l][1]+=dp[i][j][k][l];
		  dp[i+1][k][l][1]%=p;
		}

		if(k==0&&l==1)continue;
		if(k==1&&l==0)continue;
		if(k==0&&l==1)continue;
		if(j==0&&k==1)continue;
		if(j==0&&l==1)continue;

		dp[i+1][k][l][2]+=dp[i][j][k][l];
		dp[i+1][k][l][2]%=p;
	   }
	 }
    }
  }  
  ll ans=0;
  for(int j=0;j<4;j++)
    for(int k=0;k<4;k++)
	 for(int l=0;l<4;l++){
	   ans+=dp[n][j][k][l];
	   ans%=p;
	 }

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


Measured memory_bytes: 256
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "vector"
#include "string"
#include "map"
#include "algorithm"
#include "functional"
#include "set"
#include "numeric"

using namespace std;

const long long int MOD = 1000000007; 

long long int N, M, K, H, W, L, R;

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

	cin >> N >> M;
	vector<pair<int, int>>v(M);
	vector<int>used(N * 2,1);
	for (auto &i : v) {
		cin >> i.first >> i.second;
		i.first--;
		i.second--;
		if (i.first > i.second)swap(i.first, i.second);
		used[i.first]--;
		used[i.second]--;
	}
	for (int i = 1; i < N * 2; i++)used[i] += used[i - 1];
	vector<long long int>by(2 * N + 1, 1);
	for (int i = 2; i <= N * 2; i += 2) {
		by[i] = by[i - 2] * (i - 1);
		by[i] %= MOD;
	}
	vector<vector<long long int>>dp(N * 2, vector<long long int>(N * 2));
	for (int i = 1; i < 2 * N; i+=2) {
		for (int j = 0; j + i < N * 2; j++) {
			bool ed = false;
			for (auto k : v) {
				if (k.second<j || k.first>j + i || (k.first >= j && k.second <= j + i) || (k.first<j&&k.second	>j + i))continue;
				ed = true;
			}
			if (ed)continue;
			dp[j][j + i] = by[used[i + j] - (j ? used[j - 1] : 0)];
			for (int k = j + i - 2; k > j; k -= 2) {
				dp[j][j + i] += MOD;
				long long int minus = dp[j][k] * (by[used[i + j] - used[k]]);
				minus %= MOD;
				dp[j][j + i] -= minus;
			}
			dp[j][j + i] %= MOD;
		}
	}
	long long int ans = 0;
	for (int i = 0; i < N * 2; i++) {
		for (int j = i+1; j < N * 2; j++) {
			long long int add = dp[i][j];
			add *= by[used[2 * N - 1] - (used[j] - (i ? used[i - 1] : 0))];
			add %= MOD;
			ans += add;
		}
	}
	ans %= MOD;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3072
import std.stdio, std.string, std.conv;
import std.algorithm, std.array;
auto solve(string s_) {
    auto NAB = s_.split.map!(to!long)();
    immutable N=NAB[0], A=NAB[1], B=NAB[2];
    return [min(A,B),max(0,A+B-N)].map!(to!string).join(" ");
}
void main(){ for(string s; (s=readln.chomp()).length;) writeln(solve(s)); }

Measured memory_bytes: 256
n = gets.to_i

x = gets.split.map.with_index do |e, i|
    [i, e.to_i]
end.sort_by{|e| e[1]}

mid1 = x[n/2-1][1]
mid2 = x[n/2][1]


puts (x.map.with_index do |e, i|
    e << (i < n/2 ? mid2 : mid1)
end.sort_by{|e| e[0]}.map{|e| e[2]})


Measured memory_bytes: 36916
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
#define int long long
signed main(){
        char buf[4000];
        int c=0;
        map<int,int> sl;
        vector<int> f;
        while ( fgets(buf, 4000, stdin) != NULL) {
                if(buf[0]=='\n'){
                        c++;
                        continue;
                }
                int a,b;
                sscanf(buf,"%lld,%lld",&a,&b);
                if(c==0){
                        if( sl.count(a) > 0) sl[a]++;
                        else sl[a]=1;
                }else{
                        if( sl.count(a) > 0){
                                sl[a]++;
                                if(count(f.begin(),f.end(),a)==0)f.push_back(a);
                        }
                }
        }
        sort(f.begin(),f.end());
        for(auto el : f){
                cout << el << " " << sl[el] << endl;
        }
        return 0;
}

Measured memory_bytes: 3180
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<math.h>
#include<stdbool.h>
#include<vector>
#include<algorithm>
#include<string>
typedef long long ll;
using namespace std;

int main(void) {
	int a[3];
	for (int i = 0;i < 3;i++)cin >> a[i];
	sort(a, a + 3);
	cout << a[0] + a[1] << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<iomanip>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
#define LINF (long long)4e18

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;

int main(){
    string S; cin >> S;
    int cntN = 0;
    int cntS = 0;
    int cntE = 0;
    int cntW = 0;
    rep(i,S.size()){
        if(S[i] == 'N') cntN++;
        if(S[i] == 'S') cntS++;
        if(S[i] == 'E') cntE++;
        if(S[i] == 'W') cntW++;
    }
    bool ok = false;
    if(cntN && cntS && cntE && cntW) ok = true;
    else if((cntN && cntS) && (!cntE && !cntW)) ok = true;
    else if((!cntN && !cntS) && (cntE && cntW)) ok = true;
    if(ok) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int h,w;
    cin >> h >> w;
    char a[h][w];
    vector<int> v1,v2;
    for(int i = 0;i < h;i++)
    {
        for(int j = 0;j < w;j++)
        {
            cin >> a[i][j];
        }
    }
    for(int i = 0;i < h;i++)
    {
        bool flag = true;
        for(int j = 0;j < w;j++)
        {
            if(a[i][j] == '#')
            {
                flag = false;
                break;
            }
        }
        if(flag)
        {
            v1.push_back(i);
        }
    }
    for(int j = 0;j < w;j++)
    {
        bool flag = true;
        for(int i = 0;i < h;i++)
        {
            if(a[i][j] == '#')
            {
                flag = false;
                break;
            }
        }
        if(flag)
        {
            v2.push_back(j);
        }
    }
    for(int i = 0;i < h;i++)
    {
        bool flag1 = true;
        for(int k = 0;k < v1.size();k++)
        {
            if(v1.at(k) == i)
            {
                flag1 = false;
                break;
            }
        }
        if(flag1)
        {
            for(int j = 0;j < w;j++)
            {
                bool flag2 = true;
                for(int k = 0;k < v2.size();k++)
                {
                    if(v2.at(k) == j)
                    {
                        flag2 = false;
                    }
                }
                if(flag2)
                {
                    cout << a[i][j];
                }
            }
            cout << "\n";
        }
    }

    return 0;
}

Measured memory_bytes: 256
N, Y = map(int, input().split())
flag = False
for x in range(N+1):
    for y in range(N+1):
        z = N-x-y
        if z < 0:
            break
        if 10000*x + 5000*y + 1000*z == Y:
            flag = True
            print(x, y, z)
            break
    if flag:
        break
else:
    print(*[-1]*3)


Measured memory_bytes: 3060