akhauriyash/Code-Regression huggingface dataset:
/*
 * aoj/2199_2nd/main.cpp
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>

using namespace std;

#define ll long long

#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template <class T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }

const ll INF = 100000000000000000;
const int MAX_N = 20100;
const int MAX_X = 256;
ll N, M;
vector<ll> C, X;
ll dp[MAX_N][MAX_X];

bool input() {
  cin >> N >> M;
  if (N + M==0) return false;
  ll a;
  C.clear(); X.clear();
  loop(n,0,M) {
    cin >> a;
    C.push_back(a);
  }
  loop(n,0,N) {
    cin >> a;
    X.push_back(a);
  }
  return true;
}

ll rec(int n = 0, int y_1 = 128) {
  ll &cache = dp[n][y_1];
  if (~cache) return cache;
  if (n == N) return cache = 0;
  int x = X[n];
  ll min_ = INF;
  for (auto &&c: C) {
    int y = min(255LL, max(0LL, y_1 + c));
    chmin(min_, (x-y)*(x-y) + rec(n+1, y));
  }
  return cache = min_;
}

ll memo() {
  memset(dp, -1, sizeof(dp));
  return rec();
}

ll give() {
  loop(n,0,N+1) loop(x,0,MAX_X) dp[n][x] = INF;

  for (int n=0; n<N; n++) {
    int x = X[n];
    if (n == 0) {
      for (auto &&c: C) {
        int y = min(255LL, max(0LL, 128 + c));
        dp[n][y] = (x-y)*(x-y);
      }
      continue;
    }

    for (int y_1=0; y_1<=255; y_1++) {
      for (auto &&c: C) {
        int y = min(255LL, max(0LL, y_1 + c));
        chmin(dp[n][y], (x-y)*(x-y) + dp[n-1][y_1]);
      }
    }
  }

  ll min_ = INF;
  loop(x,0,MAX_X) chmin(min_, dp[N-1][x]);
  return min_;
}

void solve() {
  cout << give() << endl;
}

int main() {
  // cout.precision(15);
  while (input()) solve();
  return 0;
}



Measured memory_bytes: 43288
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

const ll MOD=1e9+7;
const ll INF=1e18;
const double pi=acos(-1);
const double eps=1e-10;

int dx[]={1, 0, -1, 0};
int dy[]={0, -1, 0, 1};

int main(){
    string s; cin>>s;
    cout << (7 < count(s.begin(), s.end(), 'x') ? "NO" : "YES") << endl;
}

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

#define LL long long
#define trio tuple<int,int,int>

using namespace std;


LL N,K,mn;

int main() {
	cin>>N>>K;
	cout<<min(N%K,K-(N%K))<<endl;
	return 0;
}



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

using namespace std;

int n;

int main(){
//	freopen("input.inp", "r", stdin);
	scanf("%d",&n);
	int cnt = 0, an = 0;
	for(int i = 1; i <= n + 1; ++i){
		int x;
		scanf("%d",&x);
		if (i > n || x != i) an += (cnt + 1) / 2, cnt = 0;
		else ++cnt;
	}
	printf("%d",an);
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <complex>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::cerr;

using std::string;
using std::to_string;
using std::vector;
using std::set;
using std::queue;
using std::stack;
using std::priority_queue;

using std::min;
using std::max;
using std::sort;
using std::abs;

typedef long long int ll;
const int MOD = 1e9 + 7;

int main() {
	int n;
	cin >> n;
	cout << n * (n + 1) / 2 << endl;
    return 0;
}



Measured memory_bytes: 504
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define SZ(a) (int)(a).size()
typedef long long ll;

bool iswin(vector<int>& a) {
	auto nodd = 0;
	for (auto x: a) {
		if (x & 1) {
			nodd++;
		}
	}
	auto neven = SZ(a)-nodd;
	if (neven & 1) {
		return true;
	}
	if (nodd > 1) {
		return false;
	}
	auto g = 0;
	for (auto& x: a) {
		if (x & 1) {
			if (x == 1) {
				return false;
			}
			x--;
		}
		g = __gcd(g, x);
	}
	for (auto& x: a) {
		x /= g;
	}
	return !iswin(a);
}

int main() {
	cin.sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> a(n);
	for (auto& x: a) {
		cin >> x;
	}
	auto ans = iswin(a);
	puts(ans ? "First" : "Second");
	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
const int INF = 1001001001;

int main() {
int N;
cin >> N;
vector<int> vec(8);
int op = 0;

for (int i = 0;i < N;i++) {
    int a;
    cin >> a;
    if (a < 400) vec.at(0) = 1;
    else if (a < 800) vec.at(1) = 1;
    else if (a < 1200) vec.at(2) = 1;
    else if (a < 1600) vec.at(3) = 1;
    else if (a < 2000) vec.at(4) = 1;
    else if (a < 2400) vec.at(5) = 1;
    else if (a < 2800) vec.at(6) = 1;
    else if (a < 3200) vec.at(7) = 1;
    else op++;
}
int cnt = 0;
for (int i = 0;i < 8;i++) {
    if (vec.at(i) == 1) cnt++;
}
if (cnt == 0) cout << 1 << " " << op << endl;
else cout << cnt << " " << cnt+op << endl;


return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, n) for (int i = (int)(n-1); i >= 0; i--)
#define sz(x) int(x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define INF 2e9
#define LINF 1e18
template<class T> inline bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> P;

int main() {
    int n; cin >> n;
    vector<int> d(n);
    rep(i, n) cin >> d[i];

    int ans = 0;
    rep(i,n)rep(j,n){
        if (i<=j) continue;
        ans += d[i]*d[j];
    }
    cout << ans << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
typedef long long ll;
typedef long double ld;
const long long INF = 1e18;
# define len(x) ((int)(x).size())
# define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
# define reps(i, n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
# define rrep(i, n) for(int i=((int)(n)-1); i>=0; --i)
# define rreps(i, n) for(int i=((int)(n)); i>0; --i)
# define foreps(i, m, n) for(int i = m;i < n;i++)
# define ALL(x) (x).begin(), (x).end()
# define rall(x) (x).rbegin(), (x).rend()
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main() {
    string S; cin >> S;
    map<char, int> ch;

    rep(i, len(S)) {
        if (ch.count(S[i])) ch[S[i]] = 1;
        else ch[S[i]] = 1;
    }
    if (ch['N'] != ch['S'] || ch['W'] != ch['E']) {
        cout << "No" << endl;
        return 0;
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 3616
from collections import deque
r, c, n = map(int, raw_input().split())
l = [list(raw_input()) for i in range(r)]
m = [[0]*c for i in range(r)]
mv = ((0,-1),(-1,0),(0,1),(1,0))
cnt = 0
k = 1
q = deque()
for i in range(r):
    for j in range(c):
        if l[i][j] == 'S':
            q.append((j, i))
def init(x,y):
    for i in range(r):
        for j in range(c):
            if x != j or y != i: m[i][j] = 0
while (k != n+1):
    x, y = q.popleft()
    if l[y][x] == str(k):
        k+=1
        init(x,y)
        cnt = m[y][x]
        q = deque()
        q.append((x, y))
        continue
    for dx, dy in mv:
        mx = x + dx
        my = y + dy
        if mx < 0 or mx >= c or my < 0 or my >= r: continue
        if l[my][mx] == 'X': continue
        if l[my][mx] != 'X' and m[my][mx] ==0:
            m[my][mx] = m[y][x] + 1
            q.append((mx, my))
print cnt

Measured memory_bytes: 32616
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define max(p,q) ((p)>(q)?(p):(q))
#define min(p,q) ((p)<(q)?(p):(q))
#define chmax(a,b) ((a)=(a)>(b)?(a):(b))
#define chmin(a,b) ((a)=(a)<(b)?(a):(b))
#define abs(p) ((p)>=(0)?(p):(-(p)))
#define MOD 1000000007
ll powll(ll a,ll b){ll r=1;rep(i,b){r*=a;}return r;}
#define swap(a,b) do{ll w=(a);(a)=(b);(b)=w;}while(0)
#define swapd(a,b) do{double w=(a);(a)=(b);(b)=w}while(0)

//your code here!
//解説カンニング

ll gcd(ll A, ll B){
    ll w;
    if(A<B) swap(A,B);
    while(B){
        w = A%B;
        A = B;
        B = w;
    }
    return A;
}

int main(void){
    ll N, A[100100], R[100100], L[100100], ans=0;
    scanf("%lld", &N);
    rep(i, N) scanf("%lld", A+1+i);
    L[0]=0; R[N+1]=0;
    for(ll i=1; i<=N-1; i++) L[i] = gcd(L[i-1], A[i]);//A[i+1] より左にある数列でのgcd
    for(ll i=N; i>=2  ; i--) R[i] = gcd(R[i+1], A[i]);//A[i-1] より右にある数列でのgcd
    for(ll i=1; i<=N; i++) chmax(ans, gcd(L[i-1], R[i+1]));
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 2560
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <cstring>
#include <math.h>
#include <bitset>
#include <time.h>
#include <set>
#include <algorithm>
#define ll long long
#define MODD 1000000007
#define ll long long
using namespace std;


ll Solve(const vector<int>& X) {
    ll ret = 0;
    int sz=X.size();
    ll summ = 0;
    for(int j=sz-1;j>=0;j--) {
        summ += X[j];
        ret += summ - (sz-j)*(ll)X[j];
    }
    ret %= MODD;
    if (ret < 0)
        ret += MODD;
    return ret;
}

int main() {
    // (xi-xj)
    int n,m;
    cin>>n>>m;
    vector<int> X(n);
    vector<int> Y(m);
    
    for(int i=0;i<n;i++)
        cin>>X[i];
    for(int j=0;j<m;j++)
        cin>>Y[j];
    
    sort(X.begin(),X.end());
    sort(Y.begin(),Y.end());
    
    
    ll ans = Solve(X)*Solve(Y)%MODD;
    if (ans < 0)
        ans += MODD;
    cout << ans%MODD << endl;
    
}

Measured memory_bytes: 1024
N = int(input())
A = list(map(int,input().split()))
left =0
right = 0
tmp = 0
for i in range(0,N-1):
    left = A[N-2-i]
    right = right + A[N-1-i]
    tmp += left * right

print(tmp%((10**9) + 7))

Measured memory_bytes: 31588
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr long long INFL = numeric_limits<long long>::max() / 2;
constexpr int MOD = 1000000007;
using Graph = vector<vector<int>>;



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

    int A,B;
    cin >> A >> B;
    if(A<10 && B<10) cout << A*B << endl;
    else cout << -1 << endl;



}


Measured memory_bytes: 256
//         PAR_YUMMM            //
                                           //           CPP                //
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

#define ll long long
#define ld long double
ll const N=1e6+5;
ll const INF=1e18;

#define pb push_back
#define popb pop_back()
#define pf push_front
#define popf pop_front()
#define si size()
#define be begin()
#define en end()
#define all(v) v.be, v.en
#define len length()
#define mp make_pair
#define mt make_tuple
#define acc(v) accumulate(all(v), 0)
#define F first
#define S second
 
#define forz(i, n) for (ll i = 0; i < n; i++)
#define fore(i, m, n) for (ll i = m; i <= n; i++)
#define rforz(i, n) for (ll i = n - 1; i >= 0; i--)
#define rfore(i, m, n) for (ll i = n; i >= m; i--)
#define deci(n) fixed << setprecision(n)
#define high(n) __builtin_popcount(n)
#define highll(n) __builtin_popcountll(n)
#define parity(n) __builtin_parity(n)
#define ctz(n) __builtin_ctz(n)
#define lb lower_bound
#define ub upper_bound
#define er equal_range
#define maxe *max_element
#define mine *min_element
#define mod 1000000007
#define mod2 998244353
#define gcd __gcd
#define sexy ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
 
#define endl "\n"
#define p0(a) cout << a << " "
#define p1(a) cout << a << endl
#define p2(a, b) cout << a << " " << b << endl
#define p3(a, b, c) cout << a << " " << b << " " << c << endl
#define p4(a, b, c, d) cout << a << " " << b << " " << c << " " << d << endl
 
#define oset tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define osetll tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
//member functions :
//1. order_of_key(k) : number of elements strictly lesser than k
//2. find_by_order(k) : k-th element in the set
#define ofk order_of_key
#define fbo find_by_order

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

ll modi(ll a,ll m){
    return po(a,m-2,m);
}

ll lcm(ll a, ll b){ 
    return (a*b)/(gcd(a, b));
}
ll max(ll a, ll b){
  if (a > b)
    return a;
  return b;
}
ll min(ll a, ll b){
  if (a < b)
    return a;
  return b;
}

ll bins(ll ar[],ll l,ll r,ll x) 
{ 
    if (r >= l) { 
        ll mid =l+((r-l)/2); 
        if(ar[mid]==x) 
            return mid; 
        if(ar[mid]>x) 
            return bins(ar,l,mid-1,x);
        return bins(ar,mid+1,r,x); 
    } 
    return -1; 
} 

ll nCr(ll n,ll k){ 
    ll C[n + 1][k + 1]; 
    ll i, j; 
    for (i=0;i<=n;i++){ 
        for(j=0;j<=min(i,k);j++){
            if(j==0||j==i) 
                C[i][j]=1;  
            else
                C[i][j]=C[i-1][j-1]+C[i-1][j]; 
        } 
    }
    return C[n][k]; 
}  

int main(){
    sexy;
    ll T,x,y,z,p,q,r,s,n,a,b;
    cin>>n>>a>>b;
    if((b-a)%2==0){
        z=(b-a)/2;
        p1((b-a)/2);
    }else{
        p1(min(a-1+1+((b-a-1)/2),n-b+1+((b-a-1)/2)));
    }
    return 0;
}


Measured memory_bytes: 256
n,m=map(int,input().split())
info=[]
for i in range(n):
    info.append(list(map(int,input().split())))
common=[info[0][i] for i in range(1,info[0][0]+1)] #最初は共通集合が１だけ
for i in range(1,n): #1～n-1
    data=[info[i][j] for j in range(1,info[i][0]+1)]
    common=set(common) & set(data)
print(len(common))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#ifdef ENABLE_DEBUG
#define dump(a) cerr<<#a<<"="<<a<<endl
#define dumparr(a,n) cerr<<#a<<"["<<n<<"]="<<a[n]<<endl
#else
#define dump(a) 
#define dumparr(a,n) 
#endif
#define FOR(i, a, b) for(ll i = a;i < b;i++)
#define For(i, a) FOR(i, 0, a)
#define REV(i, a, b) for(ll i = b-1;i >= a;i--)
#define Rev(i, a) REV(i, 0, a)
#define REP(a) For(i, a)

typedef long long int ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<ll, ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;

const ll INF=(1LL<<50);
#if __cplusplus>=201700L
ll gcd(ll a, ll b) {
  if(a < b) return gcd(b, a);
  ll r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}
#endif

template<class S,class T>
std::ostream& operator<<(std::ostream& os,pair<S,T> a){
  os << "(" << a.first << "," << a.second << ")";
  return os;
}
template<class T>
std::ostream& operator<<(std::ostream& os,vector<T> a){
  os << "[ ";
  REP(a.size()){
    os<< a[i] << " ";
  }
  os<< " ]";
  return os;
}


void solve(std::vector<long long> T, std::vector<long long> A, std::vector<long long> B){
  if(T[0]*A[0]+T[1]*A[1]==T[0]*B[0]+T[1]*B[1]){
    cout<<"infinity"<<endl;
    return;
  }
  if(T[0]*A[0]+T[1]*A[1]<T[0]*B[0]+T[1]*B[1]){
    swap(A[0],B[0]);
    swap(A[1],B[1]);
  }
  if(T[0]*(A[0]-B[0])>0){
    cout<<0<<endl;
    return;
  }
  ll diff=(T[0]*A[0]+T[1]*A[1])-(T[0]*B[0]+T[1]*B[1]);
  ll mdiff=(-T[0]*A[0]+T[0]*B[0]);
  cout<<mdiff/diff*2+(mdiff%diff>0?1:0)<<endl;
}

int main(){
    std::vector<long long> T(2);
    for(int i = 0 ; i < 2 ; i++){
        scanf("%lld",&T[i]);
    }
    std::vector<long long> A(2);
    for(int i = 0 ; i < 2 ; i++){
        scanf("%lld",&A[i]);
    }
    std::vector<long long> B(2);
    for(int i = 0 ; i < 2 ; i++){
        scanf("%lld",&B[i]);
    }
    solve(std::move(T), std::move(A), std::move(B));
    return 0;
}


Measured memory_bytes: 256
/*input
1
1

*/
 
/*
                                                    ______________
                                                          |       )
                                                          |   )   /
                                                          |______/
                                                    |     |      \
                                                    |     |   )   \
                                                    |_____|_______)
 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <iomanip>
#include <fstream>
#include <stack>

using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll , ll> PLL;
typedef long double ld;
 
#define pb push_back
#define all(c) c.begin(),c.end()
#define allr(c) c.rbegin(),c.rend()
int mod = 1000000007;
const int inf = 1034567891;
const ll LL_INF = 1234567890123456789ll;
#define PI 3.14159265
#define endl '\n'
#define F first
#define S second
#define debug(x) cout << #x << " = " << x << endl;
#define TRACE
 
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
 
#define out(container) for (auto it : container) cout << it << " "; cout << endl;
 
 
template < typename T > T GCD(T a, T b)            { ll t; while(a) { t = a; a = b % a; b = t; } return b; }
template < typename T > string toString(T a)       { return to_string(a); }
template < typename T > void toInt(string s, T &x) { stringstream str(s); str >> x;}
inline int add(int x, int y){ x += y; if(x >= mod) x -= mod; return x;}
inline int sub(int x, int y){ x -= y; if(x < 0) x += mod; return x;}
inline int mul(int x, int y){ return (x * 1ll * y) % mod;}
inline int powr(int a, ll b){
  int x = 1 % mod;
  while(b){
    if(b & 1) x = mul(x, a);
    a = mul(a, a);
    b >>= 1;
  }
  return x;
}
inline int inv(int a){ return powr(a, mod - 2);}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  int n, k;
  cin >> n >> k;
  vector<int> vec;
  int v;
  for (int i = 0; i < n; i++) {
    cin >> v;
    vec.pb(v);
  }
  sort(all(vec));
  int ans = 0;
  for (int i = 0; i < k; i++)
    ans += vec[i];
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define pi pair<int, int>
#define mk make_pair
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
const int N=2e5+10;
int n,k,c,pre[N];
char s[N];
int main()
{
    cin>>n>>k>>c;
    cin>>s+1;
    set<int>st1,st2;
    for(int i=1;i<=n;++i){
        if(s[i]=='x') continue;
        else{
            st1.insert(i);
            i+=c;
        }
    }

    for(int i=n;i>=1;--i){
        if(s[i]=='x') continue;
        else st2.insert(i),i-=c;
    }
    if(st1.size()>k||st2.size()>k) return 0;
    else{
        for(int v:st1){
            if(st2.count(v)) printf("%d\n",v);
        }
    }
}


Measured memory_bytes: 20480
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <queue>
#include <set>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <bitset>
#include <climits>
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define RFOR(i,a,b) for (int i=(a)-1;i>=(b);i--)
#define ll long long
#define ull unsigned long long
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const int INF = 1e9;
const int MOD = 1e9 + 7;
 
using namespace std;
int k;
double r,l,t,e,miss_p,suc_p;
double ans = 0.0;
void solve(int tk,double tr,double tl,double tp){
	double h = (tr+tl)/2;
	double n_suc_p = tp*suc_p;
	double n_miss_p = tp*miss_p;
	tk--;
	if(tk == -1){
		if((tr+tl)/2 >= t-e && (tr+tl)/2 <= t+e)ans+=tp;
	}else if(t+e<tr&&t+e<tl||t-e>tr&&t-e>tl)return;
	else if(h < t){
		solve(tk,h,tl,n_suc_p);
		solve(tk,tr,h,n_miss_p);
	}else{
		solve(tk,h,tl,n_miss_p);
		solve(tk,tr,h,n_suc_p);
	}
} 
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
	cin>>k>>r>>l>>miss_p>>e>>t;
	suc_p = 1.0 - miss_p;
	double p = 1.0;
	solve(k,r,l,p);
	cout.precision(10);
	cout << fixed << ans << endl;
  return 0;
}

Measured memory_bytes: 3296
#include <iostream>
#include <vector>
using namespace std;
int main(){
  int n,x;
  cin >> n >> x;
  int sum = 0;
  int min_m = 1000;
  for(int i = 0; i < n; ++i){
    int mi;
    cin >> mi;
    sum += mi;
    if(min_m > mi){
      min_m = mi;
    }
  }
  cout << (x-sum) / min_m + n << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define int long long
#define rep(i, n) for (int i = 0; i < n; i++)

#define n_l '\n'
template <typename T, size_t N> int SIZE(const T (&t)[N]) { return N; } template<typename T> int SIZE(const T &t) { return t.size(); } string to_string(const string s, int x1 = 0, int x2 = 1e9) { return '"' + ((x1 < s.size()) ? s.substr(x1, x2 - x1 + 1) : "") + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(const bool b) { return (b ? "true" : "false"); } string to_string(const char c) { return string({c}); } template<size_t N> string to_string(const bitset<N> &b, int x1 = 0, int x2 = 1e9) { string t = ""; for (int __iii__ = min(x1, SIZE(b)),  __jjj__ = min(x2, SIZE(b) - 1); __iii__ <= __jjj__; ++__iii__) { t += b[__iii__] + '0'; } return '"' + t + '"'; } template <typename A, typename... C> string to_string(const A (&v), int x1 = 0, int x2 = 1e9, C... coords); int l_v_l_v_l = 0, t_a_b_s = 0; template <typename A, typename B> string to_string(const pair<A, B> &p) { l_v_l_v_l++; string res = "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; l_v_l_v_l--; return res; } template <typename A, typename... C> string to_string(const A (&v), int x1, int x2, C... coords) { int rnk = rank<A>::value; string tab(t_a_b_s, ' '); string res = ""; bool first = true; if (l_v_l_v_l == 0) res += n_l; res += tab + "["; x1 = min(x1, SIZE(v)), x2 = min(x2, SIZE(v)); auto l = begin(v); advance(l, x1); auto r = l; advance(r, (x2 - x1) + (x2 < SIZE(v))); for (auto e = l; e != r; e = next(e)) { if (!first) { res += ", "; } first = false; l_v_l_v_l++; if (e != l) { if (rnk > 1) { res += n_l; t_a_b_s = l_v_l_v_l; }; } else { t_a_b_s = 0; } res += to_string(*e, coords...); l_v_l_v_l--; } res += "]"; if (l_v_l_v_l == 0) res += n_l; return res; } void dbgm() {;} template<typename Heads, typename... Tails> void dbgm(Heads H, Tails... T) { cout << to_string(H) << " | "; dbgm(T...); }
#define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgm(__VA_ARGS__); cout << endl

const int mod = 1e9 + 7;

int32_t main() {
   ios::sync_with_stdio(false);   cin.tie(NULL);   cout.tie(NULL);

   string s;
   int d;
   cin >> s >> d;
   int m = s.length();
   vector <vector <int>> dp(m + 1, vector <int> (d));

   vector <int> prev(d);
   for (int i = 0; i < s[0] - '0'; i++) {
      dp[0][i % d]++;
   }
   prev[(s[0] - '0') % d] += 1;

   for (int i = 1; i < m; i++) {
      for (int j = 0; j < 10; j++) {
         for (int k = 0; k < d; k++) {
            if (j < s[i] - '0') {
               dp[i][(j + k) % d] += (dp[i - 1][k] + prev[k]) % mod;
            } else {
               dp[i][(j + k) % d] += dp[i - 1][k];
            }
            dp[i][(j + k) % d] %= mod;
         }
      }
      vector <int> temp(d);
      int j = s[i] - '0';
      for (int k = 0; k < d; k++) {
         temp[(j + k) % d] += prev[k];
         temp[(j + k) % d] %= mod;
      }
      prev = temp;
   }

   cout << (dp[m - 1][0] + prev[0] - 1 + mod) % mod << '\n';

   return 0;
}

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

typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<Pii,int> Piii;
typedef pair<int,ll> Pil;
typedef pair<ll,ll> Pll;
typedef pair<string,int> Psi;
typedef pair<Psi,int> Psii;

const int inf=1000000000;
struct edge{
	int myc,to,c,cost;
};
struct pos{
	int to,cost,color;
};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

vi vec[200001];
int x[200001]={};
int dp[200001];
ll a[100001]={};
int main() {
	int n,k;
	cin>>n>>k;
	int r=0;
	rep(i,n){
		int h;
		cin>>h;
		if(h>=k)r++;
	}
	cout<<r<<endl;
	return 0;
}


Measured memory_bytes: 5248
n=int(input())
m=0
a=0
r=0
c=0
h=0


for i in range(n):
    s=input()
    if s[0]=="M":
        m+=1
    if s[0]=="A":
        a+=1
    if s[0]=="R":
        r+=1
    if s[0]=="C":
        c+=1
    if s[0]=="H":
        h+=1

l=[m,a,r,c,h]
ans=0

for i in range(2,5):
    for j in range(1,i):
        for k in range(j):
            ans+=l[i]*l[j]*l[k]
            
print(ans)



Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <bitset>
#include <cmath>
#include <iomanip>
#include <stack>
#include <set>
#include <queue>
#include <algorithm>
#include <deque>
#include <map>
#include <cmath>
#include <iomanip>
using namespace std;

#define INF 1e18
#define int long long

bool f = 0;

void dfs(string s, int i) {
    if(s == "AKIHABARA") {
        f = 1;
        return;
    }
    if(i > s.size()) return;
    dfs(s, i + 1);
    s.insert(s.begin() + i, 'A');
    dfs(s, i + 2);
}

signed main () {
    string s; cin >> s;
    if(s.size() > 9) {
        cout << "NO" << endl;
        return 0;
    }
    dfs(s, 0);
    if(!f) cout << "NO" << endl;
    else cout << "YES" << endl;
    return 0;
}


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

int main(){
    // 制約見て！！！デカかったらlong longにすること！
    int n,ans =0;
    cin >> n;
    vector<int> v(n);
    vector<int> c(n);

    rep(i,n){
        cin >> v[i];
    }

    rep(i,n){
        cin >> c[i];
    }

    rep(i,n){
        if(v[i]-c[i]>0){
            ans += v[i]-c[i];
        }
    }

    cout << ans <<endl;
}

Measured memory_bytes: 3632
c = []
for i in range(3):
    tmp = list(map(int, input().split()))
    c.append(tmp)

for irow in range(len(c)-1):
    flag = False
    for mina in range(min(c[irow])):

        b_pre = [c[irow][i] - mina for i in range(3)]
        for i in range(irow+1):
            check = [c[i+1][j] - b_pre[j] for j in range(3)]
            if len(set(check)) != 1:
                flag = True
                #break
    if flag:
        print("No")
        exit()
print("Yes")


Measured memory_bytes: 3064
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9 + 7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
#ifdef LOCAL
#define debug(x) cerr << #x << ": " << x << endl
#else
#define debug(x)
#endif
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int N;
string S;

inline vector<int> Z_algorithm(string S) {
	vector<int> A(S.size());
	A[0] = S.size();
	int i = 1, j = 0;
	while (i < S.size()) {
		while (i + j < S.size() && S[j] == S[i + j]) j++;
		A[i] = j;
		if (j == 0) i++;
		else {
			int k = 1;
			while (i + k < S.size() && k + A[k] < j) {
				A[i + k] = A[k];
				k++;
			}
			i += k;
			j -= k;
		}
	}
	return A;
}

signed main() {
	cin >> N >> S;
	ll ans = 0;
	rep(i, N) {
		string T = S.substr(i, N - i);
		vector<int> v = Z_algorithm(T);
		for (int j = 1; j < v.size(); j++) {
			if(v[j] <= j) ans = max(ans, (ll)v[j]);
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
S = input()

S_2 = list(S)



ans = []

for i in range(len(S_2)):
    if S_2[i] == "0":
        ans.append("0")
    elif S_2[i] == "1":
        ans.append("1")
    elif S_2[i] == "B" and len(ans) !=0:
        del ans[-1]

for i in ans:
    print(i,end = "")


Measured memory_bytes: 2940
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX=1e6+7;
const int mod=1e9+7;
string s[MAX];
typedef pair<string,int>pp;
ll mexp(ll a,ll b){ll res=1;while(b>0){if(b%2){res=(res*a);}a=(a*a);b=b/2;}return res;}
int main(){
	int n;
	cin>>n;
	ll alp[28];
	string s;
	cin>>s;
	memset(alp,0,sizeof(alp));
	ll res=1;
	for(int i=0;i<s.size();i++)
		alp[s[i]-'a']++;
	for(int i=0;i<26;i++)
	{
		res=res*(alp[i]+1)%mod;
		res=res%mod;
	}
	cout<<(res-1+mod)%mod;

}

Measured memory_bytes: 8320
#!/usr/bin/ruby
$c=0
def merge(a,left,mid,right)
	n1=mid-left
	n2=right-mid
	l=a[left,n1]
	r=a[mid,n2]
	l<<999999999
	r<<999999999
	i=0
	j=0
	left.step(right-1){|k|
		$c+=1
		if l[i]<=r[j]
			a[k]=l[i]
			i=i+1
		else
			a[k]=r[j]
			j=j+1
		end
	}
end

def mergesort(a,left,right)
	if left+1<right
		mid=(left+right)/2
		mergesort(a,left,mid)
		mergesort(a,mid,right)
		merge(a,left,mid,right)
	end
end

n=gets.to_i
a=gets.split.map(&:to_i)
mergesort(a,0,a.length)
puts a*' '
p $c

Measured memory_bytes: 169572
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.charset.StandardCharsets;

public class Main {
	public static void main (String[] args) throws IOException{
	    InputStreamReader reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
	    BufferedReader in = new BufferedReader(reader);
		String[] str = in.readLine().split(" ");
		int size = str.length;

		for(int i=0; i < size; i++) {
			int num = Integer.parseInt(str[i]);
			if(num == 0) {
				System.out.println(i+1);
			}
		}
	}
}

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

int main()
{

	string textS;

	cin >> textS;

	char startC = textS[0];
	bool flag = false;

	for (int i = 1; i < 3; i++)
	{
		if(textS[i] != startC){
			flag = true;
			break;
		}
	}
		
	cout << (flag ? "Yes" : "No") << endl;
	return 0;
}

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

int main(void)
{
  int n;
  int a[31]={0};

  a[0] = 1, a[1] = 1, a[2] = 2;
  

  /* a[i] Í@iiÚÉ©©éêÌ */
  for(int i = 3 ; i <= 30 ; i++)
    {
      a[i] = a[i-1] + a[i-2] + a[i-3];
    }
  
  while(cin >> n)
    {
      if(n == 0) break;
      cout << (a[n] / 10 / 365 + 1) << endl;
      // êúPOÅÁÄANÈÌÅRUTÅéBPúÅàêNvZÈÌÅPð«·
    }
  return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>

using namespace std;

#define rep(i, s, n) for(int i = s;i<n;i++)
#define repe(i, s, n) for(int i = s;i<=n;i++)
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<int> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
static const ll maxLL = (ll) 1 << 62;
const ll MOD = 1000000007, INF = 1e18;
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};

template<typename T1, typename T2>
bool pairCompare(const pair<T1, T2> &firstElof, const pair<T1, T2> &secondElof) {
    return firstElof.second > secondElof.second;
}

int mapMaxValue(std::map<ll, int> m) {
    int max = 0;
    for (std::map<ll, int>::iterator it = m.begin(); it != m.end(); it++) {
        if (max < it->second) max = it->second;
    }
    return max;
}

int main(void) {
    ll a, b;
    cin >> a >> b;
    double k = ((double) a + (double) b) / 2.0f;
    if (k - (ll) k == 0) {
        cout << (ll) k << endl;
    } else {
        cout << "IMPOSSIBLE" << endl;
    }
}

Measured memory_bytes: 256
import java.util.*;
import java.lang.*;
import java.io.*;
public class Main {
	public static void main(String[] args)
	{
		Scanner scan = new Scanner(System.in);
		int k = scan.nextInt();
		String str = scan.next();
		if(k>=str.length()) {
			System.out.println(str);
		}
		else 
		{
			System.out.println(str.substring(0,k)+"...");
		}
	}
}


Measured memory_bytes: 38460
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 1e9
#define ALL(v) v.begin(), v.end()

using namespace std;
typedef long long ll;

int main(){
    // read in integer 
    string a;
    string b;
    cin >> a >> b;
    cout << b << a << endl;

}

Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
int main(){
  int n;
  string s;
  cin >> n >> s;
  int i;
  int cnt = 0;
  for(i=0;i<n-2;i++){
    if(s.substr(i,3)=="ABC") cnt++;
  }
  cout << cnt << "\n";
  return 0;
}

Measured memory_bytes: 3600
fun main(args: Array<String>) {
    val (H, W) = listOfLong()
    val M = H * W / 2
    if (H == 1L || W == 1L) println(1)
    else {
        val ans = if (H.isOdd() && W.isOdd()) M + 1 else M
        println(ans)
    }
}
fun Long.isEven() = (this % 2L) == 0L
fun Long.isOdd() = !this.isEven()
fun next() = readLine()!!
fun nextInt() = Integer.parseInt(next())
fun nextInt(offset: Int = 0) = nextInt() + offset
fun nextLong() = java.lang.Long.parseLong(next())
fun nextLong(offset: Long = 0L) = nextLong() + offset
fun nextDouble() = next().toDouble()
fun listOfString() = next().split(" ")
fun listOfInt() = listOfString().map { Integer.parseInt(it) }
fun listOfInt(offset: Int = 0) = listOfString().map { Integer.parseInt(it) + offset }
fun listOfLong() = listOfString().map { java.lang.Long.parseLong(it) }


Measured memory_bytes: 36080
#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n;cin>>n;bool flag = true;
    map<int,int>m;
    while(n--)
    {
        int x;
        cin>>x;
        if(m[x])flag =false;
        m[x]++;
    }
    cout<<(flag?"YES":"NO");
	return 0;
}


Measured memory_bytes: 9984
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <map>
#include <set>
#include <sstream>
#include <stdio.h>
#include <cstring>

using namespace std;

#define Rep(i,a,b) for(int i = a; i < b; i++)
#define rep(i,b) Rep(i,0,b)
#define rrep(i,a) for(int i = a; i >= 0; i--)
#define allof(a) (a).begin(), (a).end()
#define pb push_back

typedef long long ll;
const int inf = 1e9 + 7;
const ll infll = 1ll << 60ll;
const ll mod = 1e9 + 7;
// 0~3までは右左下上 4~7までは斜め
constexpr int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
constexpr int dy[] = { 0, -1, 0, 1, 1, -1, -1, 1 };

/*
// 最大公約数
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}

// 最小公約数
long lcm(long a, long b) {
	return a / gcd(a, b) * b;
}*/

ll par[100000 + 10];
ll ran[100000 + 10];

// n要素で初期化
void init(int n) {
	for (int i = 0; i < n; i++) {
		par[i] = i;
		ran[i] = 0;
	}
}

// 木の根を求める
int find(ll x) {
	if (par[x] == x) {
		return x;
	}
	else {
		return par[x] = find(par[x]);
	}
}

// xとyの属する集合を併合
void unite(ll x, ll y) {
	x = find(x);
	y = find(y);
	if (x == y) return;

	if (ran[x] < ran[y]) {
		par[x] = y;
	}
	else {
		par[y] = x;
		if (ran[x] == ran[y]) ran[x]++;
	}
}

// xとyが同じ集合に属するか否か
bool same(ll x, ll y) {
	return find(x) == find(y);
}



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

	ll n, m;
	cin >> n >> m;
	vector<ll> a(m+1), b(m+1);

	for (int i = m; i > 0; i--)
		cin >> a[i] >> b[i];

	vector<ll> ans(m + 1);

	ans[0] = (n * (n - 1)) / 2;

	vector<ll> land(n, 1);


	// 計算量はO(n)かO(nlogn)

	// 端がない状態から考える

	// union-find木作成
	init(n);

	ll group = n;

	Rep(i, 1, m + 1) {
		if (same(a[i], b[i])) {
			// もとから属していたらスルー
			ans[i] = ans[i - 1];
			unite(a[i], b[i]); // 木を併合 一応
		}
		else {
			group--;
			if (group == 1) {
				unite(a[i], b[i]); // 木を併合
				ans[i] = 0;
				break;
			}
			ans[i] = ans[i - 1] - land[find(a[i])] * land[find(b[i])]; // aに属している数+bに属している数を引く
			land[find(a[i])] += land[find(b[i])];
			land[find(b[i])] = land[find(a[i])];
			unite(a[i], b[i]); // 木を併合
		}
	}

	for (int i = m - 1; i >= 0; i--) {
		cout << ans[i] << endl;
	}

	return 0;
}

Measured memory_bytes: 6016
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll>
#define P pair<ll,ll> 
#define rep(i,n) for(ll (i)=0; (i)<(n); ++(i))
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n,ans1=0,ans2=0;cin>>n;
  lvector A(n,0),B,C;rep(i,n) cin>>A[i];
  sort(A.begin(),A.end());
  B.emplace_back(A[0]);
  C.emplace_back(A[n-1]);
  ll cnt=1,posrb=n-1,poslb=1,posrc=n-2,poslc=0;
  while(cnt<n) {
    if(cnt<n) {
      B.emplace_back(A[posrb]);
      C.emplace_back(A[poslc]);
    }
    posrb--;poslc++;cnt++;
    if(cnt<n) {
      B.insert(B.begin(),A[posrb]);
      C.insert(C.begin(),A[poslc]);
    }
    posrb--;poslc++;cnt++;
    if(cnt<n) {
      B.emplace_back(A[poslb]);
      C.emplace_back(A[posrc]);
    }
    poslb++;posrc--;cnt++;
    if(cnt<n) {
      B.insert(B.begin(),A[poslb]);
      C.insert(C.begin(),A[posrc]);
    }
    poslb++;posrc--;cnt++;
  }
  rep(i,n-1) {
    ans1+=abs(B[i]-B[i+1]);
    ans2+=abs(C[i]-C[i+1]);
  }
  print(max(ans1,ans2));
  return 0;
}

Measured memory_bytes: 2804
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque




def main():
    num = int(input())
    data = [list(map(int, input().split())) for i in range(3)]

    ans = 0
    pre = -1
    for i in range(num):
        ans += data[1][data[0][i] - 1]
        if data[0][i] == pre + 1:
            ans += data[2][pre - 1]
        pre = data[0][i]
    print(ans)




if __name__ == '__main__':
    main()



Measured memory_bytes: 38508
#include<stdio.h>
#define REP(i) for((i)=0;(i)<10;(i)++)

int main(void)

{

int i ,j ,k ,l ,m=0 ,n ;



while(scanf("%d",&n) != EOF)

{

m=0 ;


REP(i){REP(j){REP(k){REP(l){if(i+j+k+l==n)m++;}}}}


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

}

return 0 ;

}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i < (b); i++)
#define rrep(i, a, b) for (int i = a; i >= (b); i--)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
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;
}
void hr() {
   cerr << "--------------" << endl;
}
const int INF = 1001001001;
const int MOD = 1000000007;

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

   int h, w, k;
   cin >> h >> w >> k;

   vector<string> c(h);
   rep(i, 0, h) cin >> c[i];

   int ans = 0;
   rep(s1, 0, 1 << h) rep(s2, 0, 1 << w) {
      ll cnt = 0;
      rep(i, 0, h) rep(j, 0, w) {
         if ((s1 >> i) & 1 || (s2 >> j) & 1) continue;
         if (c[i][j] == '#') cnt++;
      }
      if (cnt == k) ans++;
   }
   cout << ans << endl;
   return 0;
}

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

int main(){
  string S;
  cin>>S;
  int N=S.size();
  for(int i=0;i<N/2;i++)
    if(S[i]!=S[N-1-i]){
      cout<<"No"<<endl;
      return 0;
    }
  for(int i=0;i<N/4;i++)
    if(S[i]!=S[N/2-1-i]){
      cout<<"No"<<endl;
      return 0;
    }
  for(int i=0;i<N/4;i++)
    if(S[N/2+1+i]!=S[N-1-i]){
      cout<<"No"<<endl;
      return 0;
    }
  cout<<"Yes"<<endl;
}

Measured memory_bytes: 256
// https://atcoder.jp/contests/dp/tasks/dp_c
// AC 26ms 4992KB

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

#define rep(i,a,b) for (int (i) = a; (i) < b; ++(i))
#define maxi(a, b) ((a) = max((a), (b)))

int N;
ll arr[100005][3];
ll dp[100005][3];

void read() {
	cin >> N;
	rep(i,1,N+1) rep(j,0,3)
		cin >> arr[i][j];
}

void solve() {
	rep(i,0,3) dp[0][i]=0;

	rep(i,1,N+1) {
		rep(p,0,3) dp[i][p]=INT_MIN;
		rep(j,0,3) rep(k,0,3)
			if (k != j) maxi(dp[i][j], arr[i][j] + dp[i-1][k]);
	}

	ll ans = INT_MIN;
	rep(i,0,3) maxi(ans, dp[N][i]);
	cout << ans << endl;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	read();
	solve();
	return 0;
}



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

int main() {
    vector<int> n_pts;
    unordered_set<int> one_pts;
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        if(a == 1) {
            one_pts.insert(b);
        }
        if(b == n) {
            n_pts.push_back(a);
        }
    }
    bool found = false;
    for(int i = 0; i < n_pts.size(); i++) {
        if(one_pts.find(n_pts[i]) != one_pts.end()) {
            found = true;
        }
    }
    if(found) {
        cout << "POSSIBLE";
    } else {
        cout << "IMPOSSIBLE";
    }
	return 0;
}


Measured memory_bytes: 4764
#include<bits/stdc++.h>
using namespace std;
using Int = long long;

template<typename T> void chmin(T &a,T b){if(a>b) a=b;}
template<typename T> void chmax(T &a,T b){if(a<b) a=b;}

const Int MAX = 214514;
const Int INF = 1145141919810893;
Int dp[2][2][MAX];
signed main(){
  Int n;
  cin>>n;
  vector<Int> a(n);
  vector<char> b(n-1);
  for(Int i=0;i<n*2-1;i++){
    if(i&1) cin>>b[i/2];
    else cin>>a[i/2];
  }
  for(Int i=0;i<2;i++)
    for(Int j=0;j<2;j++)
      for(Int k=0;k<MAX;k++)
	dp[i][j][k]=-INF;
  
  Int sgn[]={1,-1};
  dp[0][1][0]=0;
  for(Int i=0;i<2*n-1;i++){
    Int x=i>>1;
    if(i&1){
      if(b[x]=='+'){
	for(Int j=0;j<2;j++)
	  for(Int k=0;k<2;k++)
	    chmax(dp[j][k][i+1],dp[j][k][i]);
      }else{
	for(Int j=0;j<2;j++)
	  for(Int k=0;k<2;k++)
	    chmax(dp[!j][0][i+1],dp[j][k][i]);	
      }
    }else{
      for(Int j=0;j<2;j++){
	chmax(dp[j][0][i+1],dp[j][0][i]+sgn[j]*a[x]);
	chmax(dp[!j][1][i+1],dp[j][0][i]+sgn[j]*a[x]);
	chmax(dp[j][1][i+1],dp[j][1][i]+sgn[j]*a[x]);
      } 
    }
  }

  Int ans=-INF;
  for(Int i=0;i<2;i++)
    for(Int j=0;j<2;j++)
      chmax(ans,dp[i][j][2*n-1]);
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 7936
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define fi first
#define se second
#define mp make_pair
 
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1812447359;
const ll INF = 1ll << 62;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int main(){
  int X;
  for (int i = 1; i <= 5; i++){
    cin >> X;
    if (X == 0){
      cout << i << endl;
      return 0;
    }
  }
  return 0;
}


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

#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define sc(x) scanf("%lld",&x)
#define pr(x) printf("%lld\n",x)
#define clr(x) memset(x, 0, sizeof(x))
#define all(x) x.begin(), x.end()
typedef pair<ll, ll> pii;
typedef vector< ll > vl;
typedef vector< pii > vpii;
const ll N= 1e5+55,mod = 1e9+7;
vpii v[N];
bool b[N];
ll dist[N];
void dfs(ll s){
	b[s]=true;
	ll i,j,x,y;
	for(i=0;i<v[s].size();i++){
		x=v[s][i].ff;y=v[s][i].ss;
		if(!b[x]){
			dist[x]=dist[s]+y;
			dfs(x);
		}

	}
}
int main() {
// 	freopen("Task.in","r",stdin);freopen("Task.out","w",stdout);
	ll i,j,x,y,a,b,c,n,q,k;
	sc(n);
	for(i=1;i<n;i++){
		sc(a);sc(b);sc(c);
		v[a].pb(mp(b,c));
		v[b].pb(mp(a,c));
	}
	sc(q);sc(k);
	dfs(k);
	while(q--){
		sc(x);sc(y);
		a=dist[x]+dist[y];
		pr(a);
	}
}

Measured memory_bytes: 14336
K, A, B = map(int, input().split())
maxadd = B - A
ans = 1
if(maxadd < 2):
    ans += K
else:
    K -= A - 1
    ans += A - 1
    ans += K // 2 * maxadd
    if(K%2 != 0):ans += 1
print(ans)

Measured memory_bytes: 3060
def resolve():
    H, W, K = map(int, input().split())
    c = [list(input()) for _ in range(H)]

    counter = 0
    for mask_row in range(int(1 << H) - 1):
        for mask_col in range(int(1 << W) - 1):
            black = 0
            for x in range(H):
                if f'{mask_row:b}'.zfill(H)[x] == '1':
                    continue
                for y in range(W):
                    if f'{mask_col:b}'.zfill(W)[y] == '1':
                        continue
                    if c[x][y] == '#':
                        black += 1
            if black == K:
                counter += 1
    print(counter)

if __name__ == "__main__":
    resolve()

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

using namespace std;

int main() {
    int n;
    cin >> n;
    int arr[n];
    int cpy[n];

    for (int i = 0; i<n; i++){
        cin >> arr[i];
    }
    copy(arr, arr+n, cpy);

    sort(cpy, cpy+n, greater<int>());

    int first = cpy[0];
    int second = cpy[1];


    for (int i = 0; i<n; i++){
        if (arr[i] == first){
            cout << second << endl;
        }
        else {
            cout << first << endl;
        }
    }

    return 0;
}



Measured memory_bytes: 3200
#include<bits/stdc++.h>
#include<string>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
int main(void){
    // Your code here!
    long long int n, d;
    cin >> n >> d;
    long long int count=0;
    long long int x[n];
    long long int y[n];
    
    rep(i,n){
        cin >> x[i] >> y[i];
        if((x[i]*x[i] + y[i]*y[i]) <= d*d ){
            count++;
        }
    }
    cout << count << endl;
}

Measured memory_bytes: 6756
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<vector>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<time.h>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
const double EPS=1e-10;
const int inf=1e8;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
int main(){
	int n,m;
	while(cin>>n>>m,n+m){
		vi in(n),tmp(m);
		rep(i,m)cin>>tmp[i];
		rep(i,n)cin>>in[i];
		vvi dp(n+1,vi(260));//sa 
		rep(i,n+1)rep(j,260)dp[i][j]=inf;
		dp[0][128]=0;
		
		rep(i,n){
			rep(j,260){
				if(dp[i][j]==inf)continue;
				rep(k,m){
					int d=j+tmp[k];
					if(d<0)d=0;
					if(d>255)d=255;
					dp[i+1][d]=min(dp[i+1][d],dp[i][j]+(d-in[i])*(d-in[i]));
				}
			}	
		}
		int mi=inf;
		rep(i,260)mi=min(mi,dp[n][i]);
		cout<<mi<<endl;
	}
}

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

#define int long long 
#define mod 1000000007
int dp[2*3001][2*3001];
int n,m;
void CommonSubsequence(int *A, int *B) {
    
    memset(dp, 0, sizeof dp);
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            if(A[i-1]==B[j-1]) {
                dp[i][j] = (1 + dp[i-1][j]%mod + dp[i][j-1]%mod)%mod;
            } else {
                dp[i][j] = (dp[i-1][j]%mod+dp[i][j-1]%mod-dp[i-1][j-1]%mod+mod)%mod;
            }
        }
    }    
}

#undef int 
int main(){
#define int long long
    
    cin>>n>>m;
    int s[n], t[m];
    for(int i=0;i<n;i++) cin>>s[i];
    for(int i=0;i<m;i++) cin>>t[i];
    CommonSubsequence(s,t);
    cout<<(dp[n][m]+1)%mod;
    return 0;
}



Measured memory_bytes: 281728