akhauriyash/Code-Regression huggingface dataset:
#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];
  }
  int M = 0;
  int c = 1;
  int p = 0;
  for (int i = 0; i < N; i++){
    if (A[i] > M){
      M = A[i];
      p = i;
      c = 0;
    }
    if (A[i] == M){
      c++;
    }
  }
  if (c > 1){
    for (int i = 0; i < N; i++){
      cout << M << endl;
    }
  } else {
    int M2 = 0;
    for (int i = 0; i < N; i++){
      if (i != p){
        M2 = max(M2, A[i]);
      }
    }
    for (int i = 0; i < N; i++){
      if (i == p){
        cout << M2 << endl;
      } else {
        cout << M << endl;
      }
    }
  }
}

Measured memory_bytes: 2432
#include <stdio.h>
#include <stdlib.h>

int main()
{
  int *A;
  int n,i,j,x,a;

  scanf("%d",&n);
  A=(int *)malloc(sizeof(int)*n+1);

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

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


  return 0;
}



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

int main() {
    long long MOD = 1000000007;
    int N; cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];

    long long ans = 0;
    long long pow = 1;
    for (int bit = 0; bit < 60; bit++) {
        long long one = 0;
        long long zero = 0;
        for (int i = 0; i < N; i++) {
            if (A[i] & (1LL << bit)) one++;
            else zero++;
        }
        long long sum = ((one * zero) % MOD) * (pow % MOD);
        ans = (ans + sum) % MOD;
        pow = (pow * 2) % MOD;
    }

    cout << ans << endl;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
void Main();

using i8  = int8_t;   /* -128 ~ 127 */
using u8  = uint8_t;  /* 0 ~ 255 */
using i16 = int16_t;  /* -32,768 ~ 32,767 */
using u16 = uint16_t; /* 0 ~ 65,535 */
using i32 = int32_t;  /* -2,147,483,648 ~ 2,147,483,647 */
using u32 = uint32_t; /* 0 ~ 4,294,967,295 */
using i64 = int64_t;  /* -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 */
using u64 = uint64_t; /* 0 ~ 18,446,744,073,709,551,615 */
using f32 = float;    /* (-3.4 * 10^38) ~ (3.4 * 10^38) */
using f64 = double;   /* (-1.7 * 10^308) ~ (1.7 * 10^308) */
using f80 = __float80;
template <class T> using Vec = vector<T>;
constexpr i64 INF = 1010000000000000017;
constexpr i64 MOD = 1e9 + 7;
constexpr f64 EPS = 1e-12;
constexpr f64 PI = 3.14159265358979323846;
#define YN(y, n, b) (b? y : n)
#define ALL(v) v.begin(), v.end()
#define GCD(a, b) __gcd(a, b) /* 最大公約数 */
#define LCM(a, b) a / __gcd(a, b) * b /* 最小公倍数 */

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}

void Main() {
    i32 N;
    cin >> N;
    map<i64, i32> m;
    for (i32 i = 0; i < N; i++) {
        i64 l;
        cin >> l;
        if (m.find(l) != m.end()) m[l]++;
        else m[l] = 1;
    }
    Vec<pair<i64, i32>> L;
    for (auto it = m.begin(); it != m.end(); it++) {
        L.push_back(*it);
    }
    if (L.size() < 3) {
        cout << 0 << endl;
        return;
    }
    i32 sum = 0;
    for (i32 i = 0; i < L.size() - 2; i++) {
        for (i32 j = i + 1; j < L.size() - 1; j++) {
            for (i32 k = j + 1; k < L.size(); k++) {
                if (L[i].first < L[j].first + L[k].first
                && L[j].first < L[i].first + L[k].first
                && L[k].first < L[i].first + L[j].first)
                    sum += L[i].second * L[j].second * L[k].second;
            }
        }
    }
    cout << sum << endl;
}


Measured memory_bytes: 3644
#include <stdio.h>
#include <stdlib.h>

#include <iostream>
#include <iomanip>
#include <sstream>
#include <stdint.h>
#include <string.h>

#define _USE_MATH_DEFINES
#include <math.h>

#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <string>

#include <algorithm>
#include <functional>
#include <bitset>
#include <functional>
#include <chrono>
#include <random>

#define sqr(x) (x) * (x)

typedef unsigned int u32;
typedef int i32;
typedef unsigned long long int u64;
typedef long long int i64;
typedef uint16_t u16;
typedef int16_t i16;
typedef uint8_t u8;
typedef int8_t i8;

using namespace std;
using namespace std::chrono;

const i64 mod = 1000000007ll;
const i64 smod = 998244353ll;
const i64 inf = 10000000000000007ll;

const double eps = 1e-10;

// del

const i64 MAXN = 100005;

i64 n;

i64 a[MAXN];


int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(15); cout.setf(ios::fixed);

    cin >> n;

    for (i64 i = 0; i < n; i++) {
        cin >> a[i];
    }

    i64 R = 0;
    for (i64 i = 0; i < n; i++) {
        for (i64 j = i + 1; j < n; j++) {
            R += a[i] * a[j];
        }
    }
    cout << R << endl;


    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
const ll INF = 1LL << 60;



int main(){
        ll n, k;
        cin >> n >> k;
        ll ans=n;

        if(n >= k){
            ans = n%k;
        }
        ans=min(ans,k-ans);

        cout << ans << endl;

   

}

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

using namespace std;

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

#define MAX_H 21
#define MAX_W 21
#define INF 1000000

char S[MAX_H][MAX_W];
int dist[MAX_H][MAX_W];

// ===============================

int main() {

  // -----------------------------
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  // input
  int H, W;
  cin >> H >> W;

  for (int h = 0; h < H; h++) {
    for (int w = 0; w < W; w++) {
      cin >> S[h][w];
    }
  }
  
  // -----------------------------
  
  int max_dist = 0;
  
  for (int si = 0; si < H; si++) {
    for (int sj = 0; sj < W; sj++) {

      if (S[si][sj] == '#') continue;
      
      for (int i = 0; i < H; i++) {
	for (int j = 0; j < W; j++) {
	  dist[i][j] = INF;
	}
      }
      
      queue<P> que;

      que.push( P(si, sj) );
      dist[si][sj] = 0;

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

      // BFS
      while (que.size()) {

	P p = que.front();
	que.pop();

	for (int i = 0; i < 4; i++) {

	  int nx = p.first + dx[i];
	  int ny = p.second + dy[i];

	  if ( 0 <= nx && nx < H && 0 <= ny && ny < W && S[nx][ny] != '#' && dist[nx][ny] == INF ) {
	    que.push( P(nx, ny) );
	    dist[nx][ny] = dist[p.first][p.second] + 1;
	  }
	}
      }

      int dist_goal = 0;
      for (int i = 0; i < H; i++) {
	for (int j = 0; j < W; j++) {
	  if (S[i][j] != '#') dist_goal = max(dist_goal, dist[i][j]);
	}
      }

      max_dist = max(max_dist, dist_goal);
      
    }
  }

  cout << max_dist << endl;
  
  return 0;
  
}


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

int main() {
    int n;
    cin >> n;
    vector<ll int> in(n);
    rep(i, n) cin >> in[i];
    sort(in.begin(), in.end());
    reverse(in.begin(), in.end());
    ll int ans = 0;
    rep(i, n) {
        if(i == 0) ;
        else if(i == 1) {
            ans += in[0];
//            cout << ans << endl;
        } else {
            int num = i/2;
            ans += in[num];
        }
    }

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


Measured memory_bytes: 4836
A,B,C,K = map(int,input().split())
if K <= A:
    print(K * 1)
else:
    c = A * 1
    if K <= A + B:
        pass
    else:
        if K <= A + B + C:
            c += (K - A - B) * -1
        else:
            c += C * -1
    print(c)


Measured memory_bytes: 9172
#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 <complex>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <stdio.h>

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<double> VEC;
typedef vector<VEC> MAT;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<int, PII> TIII;
typedef long long LL;
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())
#define MT(a,b,c) MP(a, MP(b, c))
#define T1 first
#define T2 second.first
#define T3 second.second

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

const LL MOD =1000000009;
int zz;
LL pe[100][10000];

void mulmatmat(LL *l, LL *r, LL *ans){
	REP(i,zz){
		FOR(j,i,zz){
			REP(k,zz){
				ans[i*75+j] = (ans[i*75+j]+l[i*75+k]*r[k*75+j])%MOD;
			}
			ans[j*75+i] = ans[i*75+j];
		}
	}
}

VLL mulmatvec(LL *l, VLL r){
	VLL ans(zz,0LL);
	REP(i,zz){
		REP(j,zz){
			ans[i]+=l[i*75+j]*r[j];
			ans[i]%=MOD;
		}
	}
	return ans;
}

VLL mulmatvec(LL k, VLL r){
	int i=0;
	VLL tr = r;
	while(k){
		if(k&1){
			tr=mulmatvec(pe[i], tr);
		}
		k>>=1;
		i++;
	}
	return tr;
}

int main(){
	int t=1;
	LL h,nb;
	while(scanf("%d%lld%lld",&zz,&h,&nb),zz){
		map<LL, VI> bar;
		VLL bary;
		memset(pe,0,sizeof(pe));
		REP(i,zz)FOR(j,max(0,i-1),min(zz,i+2))pe[0][i*75+j]=1LL;
		REP(i,65)mulmatmat(pe[i],pe[i],pe[i+1]);
		REP(i,nb){
			LL bx,by;
			scanf("%lld%lld",&bx,&by);
			bar[by].PB(bx);
			bary.PB(by);
		}
		bary.PB(h);
		SORT(bary);
		LL cur=1;
		VLL vec(zz,0);
		vec[0]=1LL;
		REP(i,bary.size()){
			LL p=bary[i]-cur;
			cur = bary[i];
			vec=mulmatvec(p,vec);
			REP(j,bar[cur].size())vec[bar[cur][j]-1]=0LL;
		}
		printf("Case %d: %lld\n", t++, vec[zz-1]);
	}
	return 0;
}

Measured memory_bytes: 9036
//#include <bits/stdc++.h>
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define FORLL(i, n, m) for(long long i = n; i < (long long)(m); i++)
#define SORT(v, n) sort(v, v+n);
#define REVERSE(v) reverse((v).begin(), (v).end())

using namespace std;
using ll = long long;
const ll MOD=1e9+7LL;
typedef pair<int, int> P;

ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }

ll factorial(ll x){
  if(x > 0) return (x * factorial(x-1)) % MOD;
  else return 1;
}

int
main(void){
  ll n, m;
  cin >> n >> m;

  if(abs(n-m)>=2) {cout << "0" << endl; return 0;}

  ll ans =  MUL(factorial(n), factorial(m));
    
  if(n == m) cout << (2*ans%MOD)%MOD << endl;
  else cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 1792
#include <stdio.h>

int parent(int k){
return k / 2;	
}
int left(int k){
return k * 2;	
}
int right(int k){
return k  *2 + 1;	
}

int main(){

    int i, jumlah, H[255];
    scanf("%d", &jumlah);
    for(i = 1; i <= jumlah; i++){
    	scanf("%d", &H[i]);
	}
    
    for(i = 1 ; i <= jumlah ; i++) {
        printf("node %d: key = %d, ", i, H[i]);
        if(parent(i) >= 1) printf("parent key = %d, ", H[i / 2]);
        if(left(i) <= jumlah) printf("left key = %d, ", H[i * 2]);
        if(right(i) <= jumlah) printf("right key = %d, ", H[i * 2 + 1]);
        printf("\n");
    }
    return 0;
}


Measured memory_bytes: 2148
#include <iostream>
using namespace std;
int main( ){
  int H,W;
  while(true){
     cin>>H;
     cin>>W;
     if(H==0 && W==0){
         break;
     }
        for ( int j = 0; j < W; j++ ){
            cout<<'#';
        }
        cout<<endl;
        for(int i=1; i<H-1; i++){
            cout<<'#';
            for(int j=1;  j<W-1; j++){
                cout<<'.';
            }
            cout<<'#'<<endl;
        }
        for(int j=0; j<W; j++){
            cout<<'#';
        }
        cout<<endl<<endl;
  }
}
       


Measured memory_bytes: 3000
#include<stdio.h>

 int main ()
 {
     char str[20],s2[20];

     scanf("%s",str);
     int i,len=0;

     for (i=0;str[i]!='\0';i++)
     {
         len++;
     }
     for (i=0 ; i<len ; i++ )
     {
         s2[len-1-i] = str[i];
     }
     s2[len-1-i]='\0';
     for (i=0;i<len;i++)
     printf ("%c", s2[i]);
     printf ("\n");
     return 0;
 }

Measured memory_bytes: 524
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T, class U> void assign(V<T>& v, int n, const U& a) { v.assign(n, a); }
template<class T, class... Args> void assign(V<T>& v, int n, const Args&... args) { v.resize(n); for (auto&& e : v) assign(e, args...); }


int main() {
  cin.tie(nullptr); ios_base::sync_with_stdio(false);
  auto clamp = [](int x) -> int {
    return min(max(x, 0), 255);
  };
  while (true) {
    int n, m; cin >> n >> m;
    if (n == 0) break;
    V<> c(m);
    for (auto&& e : c) cin >> e;
    V<> x(n);
    for (auto&& e : x) cin >> e;
    VV<> dp(n + 1, V<>(256, 2e9));
    dp[0][128] = 0;
    for (int i = 0; i < n; ++i) {
      for (int p = 0; p < 256; ++p) {
        for (int j = 0; j < m; ++j) {
          int q = clamp(p + c[j]);
          dp[i + 1][q] = min(dp[i + 1][q], dp[i][p] + (x[i] - q) * (x[i] - q));
        }
      }
    }
    int res = *min_element(begin(dp[n]), end(dp[n]));
    cout << res << '\n';
  }
}


Measured memory_bytes: 23848
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>

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

using namespace std;

struct E{
	int a, b, c;
};

typedef pair<int, int> P;
typedef pair<int, P> PP;
typedef vector<int> V;
typedef vector<E> VE;
typedef vector<VE> VVE;

const int inf = 1e6;

int n, m;
int p[200000];
int q[200000];
int c[200000];
V k[100000];
VVE g[100000];
V d[100000];

void make_graph(){
	rep(i, m){
		k[p[i]].push_back(c[i]);
		k[q[i]].push_back(c[i]);
	}
	rep(i, n){
		k[i].push_back(0);
		sort(k[i].begin(), k[i].end());
		k[i].erase(unique(k[i].begin(), k[i].end()), k[i].end());
		g[i].resize(k[i].size());
		for(int j = 1; j < g[i].size(); ++j){
			g[i][0].push_back({i, j, 1});
			g[i][j].push_back({i, 0, 0});
		}
	}
	rep(i, m){
		int a = lower_bound(k[p[i]].begin(), k[p[i]].end(), c[i]) - k[p[i]].begin();
		int b = lower_bound(k[q[i]].begin(), k[q[i]].end(), c[i]) - k[q[i]].begin();
		g[p[i]][a].push_back({q[i], b, 0});
		g[q[i]][b].push_back({p[i], a, 0});
	}
}

void dijkstra(){
	rep(i, n){
		d[i].resize(g[i].size(), inf);
	}
	priority_queue<PP, vector<PP>, greater<PP>> q;
	d[0][0] = 0;
	q.push({0, {0, 0}});
	while(!q.empty()){
		PP v = q.top();
		q.pop();
		P& p = v.second;
		if(d[p.first][p.second] < v.first){
			continue;
		}
		for(E& e: g[p.first][p.second]){
			if(d[e.a][e.b] > v.first + e.c){
				d[e.a][e.b] = v.first + e.c;
				q.push({d[e.a][e.b], {e.a, e.b}});
			}
		}
	}
}

int main(){
	scanf("%d%d", &n, &m);
	rep(i, m){
		scanf("%d%d%d", &p[i], &q[i], &c[i]);
		--p[i];
		--q[i];
	}

	make_graph();

	dijkstra();

	int ans = inf;
	for(int v: d[n - 1]){
		ans = min(v, ans);
	}
	printf("%d\n", (ans != inf ? ans : -1));
	return 0;
}

Measured memory_bytes: 52592
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <stdio.h>

using namespace std;

//typedefリスト
typedef vector<int> vint;
typedef vector<string> vstr;


int main(void) {
	int N, A, B,ans,n,sum;
	string I;
	ans = 0;
	cin >> N >> A >> B;
	for (int i = 1; i <= N; i++) {
		sum = 0;
		I = to_string(i);
		n = I.length();
		for (int j = 0; j < n; j++) {
			sum += I[j] - '0';
		}
		if (A <= sum && sum <= B)ans += i;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <complex>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define MOD 1000000007
#define MOD2 998244353
#define PRIM 3
#define INF (1 << 29)
#define LINF (1LL << 60)
#define EPS (1e-10)
#define PI 3.1415926535897932384626433832795028
typedef long long Int;
typedef pair<Int, Int> P;
typedef long double Real;
typedef complex<Real> CP;
int a[220000], b[220000];
int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    while (k--) {
        bool done = true;
        for (int i = 0; i < n; i++) {
            int l = i - a[i];
            int r = i + a[i] + 1;
            l = max(l, 0);
            r = min(r, n);
            b[l]++;
            b[r]--;
        }
        for (int i = 1; i < n; i++) {
            b[i] += b[i - 1];
        }
        for (int i = 0; i < n; i++) {
            if (a[i] != b[i])
                done = false;
            a[i] = b[i];
            b[i] = 0;
        }
        b[n] = 0;
        if (done)
            break;
    }
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;
    return 0;
}

Measured memory_bytes: 4732
//#include <atcoder/modint>
#include <bits/stdc++.h>
using namespace std;
//using namespace atcoder;
typedef long long ll;
#define REP(i, n) for(int i=0; i<n; i++)
#define REPR(i, n) for(int i=n-1; i>=0; i--)
#define FOR(i, m, n) for(int i=m; i<n; i++)
#define ALL(v) v.begin(), v.end()
#define SIZE(x) ll(x.size()) 
using P = pair<int, int>;
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; }
const int INF = 2e9;
const ll LINF = (1LL<<60);

const int mod = 1000000007;
//const int mod = 998244353;
struct mint {
  ll x;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n; cin >> n;
  if(n==1){
    cout << 0 << endl;
    return 0;
  }

  mint ans = mint(10).pow(n);
  ans -= mint(9).pow(n) * mint(2);
  ans += mint(8).pow(n);

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3636
import fractions


def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


n, m = map(int, input().split())
v = list(map(int, input().split()))
num = 0
# print(v[0])
while (v[0] % 2 == 0):
    v[0] //= 2
    num += 1
# print(v[0])
ans = v[0]
for i in range(n - 1):
    if (v[i + 1] % (2 ** num) != 0 or v[i + 1] % (2 ** (num + 1)) == 0):
        ans = 2
        break
    # print(v[i+1])
    v[i+1] //= 2**num
    # print(v[i+1])
    ans = lcm(ans, v[i + 1])
# print(ans)
if (ans % 2 == 0):
    print(0)
    exit(0)
ans *= 2**(num-1)
print(((m//ans)+1)//2)


Measured memory_bytes: 89580
import java.util.Scanner;

public class Main {

    public static void main(String args[]) {

        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String t = sc.next();
        int a = Integer.parseInt(sc.next());
        int b = Integer.parseInt(sc.next());
        String u = sc.next();

        a = u.equals(s) ? a - 1 : a;
        b = u.equals(t) ? b - 1 : b;

        System.out.println(a + " " + b);

        sc.close();
    }
}


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

typedef long long ll;

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

int main()
{
    string S;
    cin >> S;

    for(int i=0; i<S.length(); i++){
        cout << "x";
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 256
using System;
namespace q1
{
    class q2
    {
        static void Main()
        {
            int K = int.Parse(Console. ReadLine());
            string[] AB = Console.ReadLine().Split();
            int A = int.Parse(AB[0]);
            int B = int.Parse(AB[1]);
            if((A-1)/K==B/K)
            {
                Console.WriteLine("NG");
            }
            else
            {
                Console.WriteLine("OK");
            }
        }
    }
}


Measured memory_bytes: 27416
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right


# https://atcoder.jp/contests/abc159/tasks/abc159_d
# Kを抜かないときは簡単
# その数字のカウントをnとするとnC2通り
# k番目の数字を抜く kが減る→ n-1 C 2通りになる

# カウントn1,n2...とすると sum (n1,n2...) nC2 で
# kのカウントにnkについて通りを引いて新しい通りに更新してやれば良い

N = read_a_int()
A = read_ints()
cnt = Counter(A)
s = 0
for v in cnt.values():
    s += v * (v - 1) // 2

for a in A:
    n = cnt[a]
    ans = s - (n * (n - 1) // 2) + ((n - 1) * (n - 2) // 2)
    print(ans)


Measured memory_bytes: 82764
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,N) for(int i = 0;i < (int)(N);i++)
int main(){
int n;
  cin>>n;
  vector<int>p(n),q(n);
  rep(i,n) cin>>p[i];
  rep(i,n) cin>>q[i];
  vector<int>a(n);
  rep(i,n) a[i]=i+1;
  
  map<vector<int>,int> mp;
  do{
    mp[a]=mp.size();
  }while(next_permutation(a.begin(),a.end()));
  int ans=abs(mp[p]-mp[q]);
              cout<<ans<<endl;
               }
  


Measured memory_bytes: 6528
#include<stdio.h>
int main(void){
  char s[1001];
  int i,j,flag=0;
  scanf("%s",s);
  for(i=0;flag==0;i++){
    if(s[i]=='\0'){
      j=i;
      flag=1;
    }
  }
   if(s[j-1]=='s'){
     s[j]='e';
     s[j+1]='s';
     s[j+2]='\0';
   }
    else{
      s[j]='s';
      s[j+1]='\0';
    }
  printf("%s",s);
 return 0;
}

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

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

    char s[100+1];

    scanf("%s", s);

    int n = strlen(s);

    rep(i, n)
    if(i%2 == 0)
    {
        if (s[i] == 'L') {
            puts("No");
            return 0;
        }
    } else {
        if (s[i] == 'R') {
            puts("No");
            return 0;
        }
    }

    puts("Yes");
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};

typedef struct node *Node;
Node root;

Node find(Node x,int k){
  if(x  == NULL || k == x->key)return x;
  if(k < x->key)return find(x->left,k);
  else return find(x->right,k);
}




void insert(int k){
  Node y = NULL;//x??????
  Node x = root;//t????????£???
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NULL;
  z->right = NULL;

  while(x != NULL){
    y = x;
    if(z->key < x->key)x = x->left;
    else x = x->right;
  }

  z->parent = y;

  if( y == NULL )root = z;
  else if(z->key < y->key) y->left = z;
  else y->right = z;

}

//ok inorder
void inorder(Node u){
  if(u->left != NULL)inorder(u->left);
  printf(" %d",u->key);
  if(u->right != NULL)inorder(u->right);
}


//ok preorder
void preorder(Node u){
  printf(" %d",u->key);
  if(u->left != NULL)preorder(u->left);
  if(u->right != NULL)preorder(u->right);
}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);

    if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    }
    else if(com[0] =='f'){
      scanf("%d",&x);
      Node t = find(root,x);
      if( t!= NULL )printf("yes\n");
      else printf("no\n");
    }
    else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
  }
  return 0;
}

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

using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define MIN(a,b) ((a)>(b)? (b): (a))
#define MAX(a,b) ((a)<(b)? (b): (a))

const long long INF = 1LL << 60;
typedef unsigned long long ll;
const long long MOD = 1000000000 + 7;

int main(){
    int H, W;
    cin >> H >> W;
    string s[H];
    rep(i, H) cin >> s[i];
    rep(i, W+2) cout << '#';
    cout << endl;
    rep(i, H)
    {
        cout << '#';
        cout << s[i];
        cout << '#' << endl;
    }
    rep(i, W + 2) cout << '#';
    return 0;
}

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

int main() {
	string str;
	cin >> str;
	int sum = 0;
	for (int i = 0; i < str.size(); i += 2){
		if (str.at(i) == 'R' || str.at(i) == 'U' || str.at(i) == 'D') {
			sum++;
		}
	}
	for (int i = 1; i < str.size(); i += 2) {
		if (str.at(i) == 'L' || str.at(i) == 'U' || str.at(i) == 'D') {
			sum++;
		}
	}
	/*cout << sum;
	cout << str.size();*/

	int a = str.size();
	if (sum == a) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}


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

int main(){
    int N;
    cin >> N;
    int A[N+1];
    int B[N+1];

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

    for(int i = N; i > 0; i--){
        int k = N/i;
        int s = A[i];
        for(int j = 2; j <= k; j++){
            s += B[j*i];
        }
        B[i] = s % 2;
    }

    int count = 0;

    for(int i = 1; i <= N; i++){
        count += B[i];
    }

    cout << count << endl;

    for(int i = 1; i <= N; i++){
        if(B[i] == 1){
            cout << i << endl;
        }
    }
}

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

int R;
int main () {
	cin >> R;
	if (R < 1200) {
	cout << "ABC" << endl;
	}else if (R < 2800) {
	cout << "ARC" << endl;
	}else {
	cout << "AGC" << endl;
}	
return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <limits>
#include <cmath>
#include <numeric>
#include <string>

using namespace std;

using ll = long long int;
using ull = unsigned long long int;
#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 REP(i, a, b) for(int i = (a); i <= (b); ++i )
#define RREP(i, a, b) for(int i = (a); i >= (b); --i )
#define ullrep(i, a, b) for(ull i = (a); i < (b); ++i )
#define ullrrep(i, a, b) for(ull i = (a); i > (b); --i )
#define ullREP(i, a, b) for(ull i = (a); i <= (b); ++i )
#define ullRREP(i, a, b) for(ull i = (a); i >= (b); --i )


ll N;
ll A[200003];

int main() {
    cin >> N;
    A[0] = 0;
    for (ll i = 1; i <= N; i++) {
        ll a;
        cin >> a;
        A[i] = A[i-1] + a;
    }
    ll cnt = 0;
    std::sort(A, A+N+1);
    ll k = 1;
    ll z = 0;
    for (ll i = 0; i <= N; i++) {
        if (A[i] == A[i-1] && (A[i] != 0)) {
            k++;
        }else{
            cnt += k*(k-1)/2;
            k = 1;
        }
        if (A[i] == 0) {
            z++;
        }
    }
    if (k != 1) {
        cnt += k*(k-1)/2;
    }
    z = z - 1;
    if (z > 0) {
        cnt += z + (z * (z-1))/2;
    }
    cout << cnt << endl;
}

Measured memory_bytes: 1792
#include<iostream>
using namespace std;
int main(){
    int A,B,ans;
    cin >> A;
    cin >> B;
    if(B%A == 0){
        ans = A+B;
        cout << ans << "\n";
    }
    else{
        ans = B-A;
        cout << ans << "\n";
    }
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n = 0, a;
  for (int i = 0; i<3; i++){
    cin >> a;
    n += a;
  }
  if(n>=22){
    cout << "bust" << "\n";
  }else{
    cout << "win" << "\n";
  }

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
const ll MOD = 998244353;
const ll INF = 1e18;
using namespace std;


main(){    
    #ifdef XOX
        freopen("D:\\V S Code\\cpp\\competitiveProgramming\\Input.txt", "r", stdin);
        freopen("D:\\V S Code\\cpp\\competitiveProgramming\\OPT.txt", "w", stdout);
    #endif

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    string s, t;
    cin >> s >> t;

    int n = s.length();
    bool state = true;
    for(int i = 0; i < n; i++){
        if(s[i] != t[i])    state = false;
    }

    if(state)   {
        cout << "Yes";
        return  0;
    }

    for(int i = 0; i < n; i++){
        if(s[i] != t[i + 1])    state = false;
    }

    if(state)   cout << "Yes\n";
    else    cout << "No\n";
}

Measured memory_bytes: 3652
p=print
r=range
def a(i,j,k,l=0):p("+<"[l],i,j,k)
def b(i):a(i,i,i+1)
def d(x,i):
	for t in r(30):b(p:=i+t+30);a(q:=p+1,n,q);[*map(b,r(q,v:=i+60))];a(v,x,i+t,1);b(p);a(q,i+t,q)
p(n:=3934)
a(0,1,n)
a(2,n,n,1)
a(0,n,0)
a(1,n,1)
d(0,9)
d(1,50)
for t in r(60):a(2,2,2);[t-31<s<30!=(a(8+t-s,50+s,5),a(n,5,6,1),a(2,6,2))for s in r(t)]

Measured memory_bytes: 9160
#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 H, W, N, m;
    cin >> H >> W >> N;
    m = max(H, W);
    cout << (N + m - 1) / m << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

struct node {
	struct node *right;
	struct node *left;
	struct node *parent;
	int key;
};

typedef struct node * Node;
#define NIL NULL

Node root = NIL;

Node treeSearch(Node root, int k) {
	if (root == NIL) return NIL;
	if (root->key == k) return root;
	if (root->key > k) {
		if (root->left != NIL) return treeSearch(root->left, k);
		else return NIL;
	} else {
		if (root->right != NIL) return treeSearch(root->right, k);
		else return NIL;
	}
}

int find(Node root, int k) {
	if (root->key == k) return 1;
	if (root->key < k) {
		if (root->left != NIL) return find(root->left, k);
		else return 0;
	} else {
		if (root->right != NIL) return find(root->right, k);
		else return 0;
		
	}
}

void insert(int k) {
	Node y = NIL;
	Node x = root;
	Node z;

	z = malloc(sizeof(struct node));
	z->key = k;
	z->left = NIL;
	z->right = NIL;

	while (x != NIL) {
		y = x;
		if (z->key < x->key) {
			x = x->left;
		} else {
			x = x->right;
		}
	}
	
	z->parent = y;
	
	if (y == NIL) {
		root = z;
	} else if (z->key < y->key) {
		y->left = z;
	} else {
		y->right = z;
	}
}

void inorder(Node u) {
	if (u == NIL) return;
	inorder(u->left);
	printf(" %d", u->key);
	inorder(u->right);
	return;
}

void preorder(Node u) {
	if (u == NIL) return;
	printf(" %d", u->key);
	preorder(u->left);
	preorder(u->right);
	return;
}

Node getMinimum(Node u) {
	while (u->left != NIL) {
		u = u->left;
	}
	return u;
}

Node getSuccessor(Node u) {
	Node y;
	if (u->right != NIL) {
		return getMinimum(u->right);
	}
	
	y = u->parent;
	
	while (y != NIL && u == y->right) {
		u = y;
		u = y->parent;
	}
	return y;
}

void treeDelete(Node z) {
	Node y;
	Node x;
	if (z->left == NIL || z->right == NIL) {
		y = z;
	} else {
		y = getSuccessor(z);
	}

	if (y->left != NIL) {
		x = y->left;
	} else {
		x = y->right;
	}

	if (x != NIL) {
		x->parent = y->parent;
	}

	if (y->parent == NIL) {
		root = x;
	} else if (y == y->parent->left) {
		y->parent->left = x;
	} else {
		y->parent->right = x;
	}

	if (y != z) {
		z->key = y->key;
	}
	
	free(y);
	return;
}

int main(void) {
	int n, i, x;
	char com[20];
	scanf("%d", &n);

	for (i = 0; i < n; ++i) {
		scanf("%s", com);
		if ( com[0] == 'f' ) {
			scanf("%d", &x);
			Node t = treeSearch(root, x);
			if ( t != NIL ) printf("yes\n");
			else printf("no\n");
		} else if ( com[0] == 'i') {
			scanf("%d", &x);
			insert(x);
		} else if ( com[0] == 'p') {
			inorder(root);
			printf("\n");
			preorder(root);
			printf("\n");
		} else if ( com[0] == 'd') {
			scanf("%d", &x);
			treeDelete(treeSearch(root, x));
		} 
	}
	
	return 0;
}

Measured memory_bytes: 19364
/*

*/
#include<iostream>
#include<iomanip>
#include<ios>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<algorithm>
#include<utility>
#include<math.h>
#include<cstdlib>
#define rep(i, n) for(int i=0;i<n;i++)
#define repb(i, a, b) for(int i=a;i<b;i++)
#define MAX_N 10000

using namespace std;
typedef pair<int, int> P;
typedef long long int ll;

const int INF = 1<<30;
const ll MOD = ll(1e9+7);

int field[101][101];

int main(){
  int h, w;cin>>h>>w;
  int n;cin>>n;
  int x=0, y=0;
  rep(i, n){
    int a;cin>>a;
    while(a>0){
      if((x&1)==0){
        for(;y<w;y++){
          if(a--<=0)break;
          field[x][y]=i+1;
        }
      }else{
        for(;y>=0;y--){
          if(a--<=0)break;
          field[x][y]=i+1;
        }
      }
      if(y==w){x++;y--;}
      else if(y==-1){x++;y++;}
    }
  }
  rep(i, h){
    rep(j, w){
      cout<<field[i][j]<<" ";
    }
    cout<<endl;
  }
  // system("read -n 1 -s -p \"Press any key to continue...\"");
}


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

int main(){
	string s,t;
	cin >> s >> t;
	
	int ans = 0;
	if(s.at(0) == t.at(0)) ans++;
	if(s.at(1) == t.at(1)) ans++;
	if(s.at(2) == t.at(2)) ans++;

	cout << ans << endl;

	return 0;
}

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

int main() {
	// your code goes here
	ll k;
	cin >> k;
	ll sum = 0;
	for(ll i = 1; i <= k; i++){
	    for(ll j = 1; j <= k; j++){
	        ll hcf = __gcd(i, j);
	        for(ll l = 1; l <= k; l++){
	            sum += __gcd(hcf, l);
	        }
	    }
	}
	cout << sum << endl;
	return 0;
}


Measured memory_bytes: 3620
///Bismillahir Rahmanir Rahim
#include "bits/stdc++.h"

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

using namespace std;

const ll inf=1e18;
const int mod=1e9+7;
const int M=100005;

 main()

{
    fast
    int n;
    cin>>n;
    int a[n+2],b[n+2];
    int sum=0;
    f(i,1,n)
    {
        cin>>a[i];
        sum=sum^a[i];
    }
    for(int i=1;i<=n;i++)
    {
        b[i]=sum^a[i];
    }
    f(i,1,n)
    {
        cout<<b[i]<<" ";
    }
    cout<<endl;
    return 0;

}





































Measured memory_bytes: 6620
import bisect
import sys
import math
input = sys.stdin.readline
import functools

from collections import defaultdict

############ ---- Input Functions ---- ############

def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def invr():
    return(map(int,input().split()))

############ ---- Solution ---- ############

def diff(S, i, T):
    res = 0
    for j in range(len(T)):
        if S[i + j] != T[j]:
            res += 1
    return res

def solve():
    N = inp()
    AA = inlt()
    M = 10 ** 9 + 7
    s = 0
    res = 0
    for i in range(N - 1, 0, -1):
        s = (s + AA[i]) % M
        res = (res + (AA[i - 1] * s) % M) % M
    return res

    

if len(sys.argv) > 1 and sys.argv[1].startswith("input"):
    f = open("./" + sys.argv[1], 'r')
    input = f.readline

res = solve()
print(str(res))


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

sys.setrecursionlimit(10**5)


def yes():
    print("YES")  # type: str


def no():
    print("NO")  # type: str


template = ["dream", "dreamer", "erase", "eraser"]


def dfs(s, i):
    if i == len(s):
        return True
    for t in template:
        if s[i:].startswith(t):
            if dfs(s, i+len(t)):
                return True
    return False


def solve(S: str):
    if dfs(S, 0):
        yes()
    else:
        no()

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)


if __name__ == '__main__':
    main()


Measured memory_bytes: 19156
#include <bits/stdc++.h>
#include <string>
#include <cmath>
#include <sstream>
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FORD(i, a, b) for(int i = (a); i >=(b); i--)
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
typedef long long int ll;
using namespace std;
ll mod1=1000000007;
ll mod2=67280421310721;
ll mod3=998244353;
ll INF=1e18;

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

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

ll gcd(ll a,ll b){
    if (b==0)
        return a;
    else
        return gcd(b,a%b);
}

ll dp[100001][4];ll a[100001];ll b[100001];ll c[100001];ll n;

ll func(ll flag,ll day)
{
    if(dp[day][flag]!=-1)
    {
        return dp[day][flag];
    }
    ll maxi;
    if(day==n)
    {
        if(flag==0)
        {
            maxi=max(a[day-1],b[day-1]);
            maxi=max(maxi,c[day-1]);
        }
        else if(flag==1)
        {
            maxi=max(b[day-1],c[day-1]);
        }
        else if(flag==2)
        {
            maxi=max(a[day-1],c[day-1]);
        }
        else if(flag==3)
        {
            maxi=max(b[day-1],a[day-1]);
        }
    }
    else
    {
        if(flag==0)
        {
            maxi=max(func(1,day+1)+a[day-1],func(2,day+1)+b[day-1]);
            maxi=max(maxi,func(3,day+1)+c[day-1]);
        }
        else if(flag==1)
        {
            maxi=max(func(2,day+1)+b[day-1],func(3,day+1)+c[day-1]);
        }
        else if(flag==2)
        {
            maxi=max(func(1,day+1)+a[day-1],func(3,day+1)+c[day-1]);
        }
        else if(flag==3)
        {
            maxi=max(func(2,day+1)+b[day-1],func(1,day+1)+a[day-1]);
        }
    }
    dp[day][flag]=maxi;
    return maxi;
}

int main()
{ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    cin>>n;
    FOR(i,0,n)
    {
        cin>>a[i]>>b[i]>>c[i];
    }
    FOR(i,0,100001)
{
    FOR(j,0,4)
    {
        dp[i][j]=-1;
    }
}
    ll ans=func(0,1);
    cout<<ans<<'\n';



	return 0;
}













Measured memory_bytes: 13780
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;

#define REP(i,a,b) for(i=a; i<b; ++i)
#define rep(i,n) REP(i,0,n)
#define pdd pair<double,double>
#define fi first
#define se second
const double inf = 1e12;
const double eps = 1e-9;

double d[22][22];
int n,hx,hy,dx,dy,i,x,y,j;
bool flag;

double dist(double ax,double ay,double bx,double by) {
  return sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by));
}

bool rec(int npos,int visited,double time,int vc) {
  //cout<<npos<<" "<<time<<" "<<vc<<" "<<n<<endl;

  for(int k=2; k<n+2; ++k) {
    if((1<<k) & visited) continue;
    if(d[npos][k]+time - d[1][k] >= -eps) return false;
  }
  if(vc >= n) return true;
  for(int k=2; k<n+2; ++k) {
    if((1<<k) & visited) continue;
    if(d[npos][k]+time - d[1][k] >= -eps) break;
    if(rec(k, visited|(1<<k), d[npos][k]+time, vc+1)) return true;
  }
  return false;
}

int main() {
  while(cin>>n>>hx>>hy>>dx>>dy, n|hx|hy|dx|dy) {
    vector<pdd > in;
    in.push_back(pdd(hx,hy));
    in.push_back(pdd(dx,dy));
    rep(i,n) {
      cin>>x>>y;
      in.push_back(pdd(x,y));
    }

    rep(i,22) rep(j,22) d[i][j] = inf;
    rep(i,n+2) rep(j,n+2) {
      if(i == j) d[i][j] = 0.0;
      d[i][j] = dist(in[i].fi, in[i].se, in[j].fi, in[j].se);
    }

    if(rec(0,0,0.0,0)) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
  }
}

Measured memory_bytes: 912
import sys
from bisect import bisect_left

n = int(input())
a = tuple(map(int,sys.stdin.readline().split()))
q = int(input())

l = len(a)
for k in sys.stdin:
    k = int(k.strip())
    if k > a[-1]:print(l)
    else:
        print(bisect_left(a,k))


Measured memory_bytes: 16868
n=int(input())
a=[]
xy=[]
for i in range(n):
  a+=[int(input())]
  tmp=[]
  for j in range(a[-1]):
    tmp+=[list(map(int,input().split()))]
  xy+=[tmp]

ans=0
for i in range(2**n):
  flg=list(map(int,bin(i)[2:].zfill(n)))
  s=0
  for j in range(n):
    if flg[j]==1:
      for k in range(a[j]):
        if flg[xy[j][k][0]-1]!=xy[j][k][1]:
          s=1
  if s==0:
    ans=max(ans,sum(flg))
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#define lli long long
using namespace std;

template<class T>
lli C(T k, T n) {
    lli res = 1;
    for (T i = 1; i <= k; i++,n--)
        res = res * n / i;
    return res;
}

int main() {
    lli n;
    cin >> n;
    cout << C(2ll,n) - C(2ll,n/2) - C(2ll,(n>>1)+(n&1));
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main()
        {
            for (; ; )
            {
               
               
                string a = Console.ReadLine();
                int ab = int.Parse(a);
                if (ab == 0)
                {
                    break;
                }
                int b;

                for (b = 0; b < 9; b++)
                {
                    string c = Console.ReadLine();
                    int d = int.Parse(c);
                    ab = ab - d;
                }
                Console.WriteLine(ab);
            }
        }
    }
}

Measured memory_bytes: 5604
#include<cstdio>
#include<vector>
#include<algorithm>

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

using namespace std;

const int N_MAX=100;

int match[2][N_MAX];
#define slack(u,v) (lbl[0][u]+lbl[1][v]+a[u][v])
template<class cost_t>
cost_t Kuhn_Munkres(int n,const cost_t a[N_MAX][N_MAX]){
	const cost_t COST_INF=1<<29;

	static cost_t lbl[2][N_MAX];
	rep(i,2) rep(u,n) match[i][u]=-1, lbl[i][u]=0;

	rep(root,n){
		static bool S[N_MAX],T[N_MAX];
		static int pre[N_MAX],u_min[N_MAX];
		rep(u,n) S[u]=false;
		rep(v,n) T[v]=false, pre[v]=-1, u_min[v]=root;
		S[root]=true;

		while(1){
			cost_t d=COST_INF;
			rep(v,n) if(!T[v]) d=min(d,slack(u_min[v],v));
			rep(u,n) if( S[u]) lbl[0][u]-=d;
			rep(v,n) if( T[v]) lbl[1][v]+=d;

			int x,y;
			rep(v,n) if(!T[v] && slack(u_min[v],v)==0) { y=v; break; }
			x=match[1][y];
			pre[y]=u_min[y];

			if(x==-1){
				while(y!=-1){
					int w=pre[y];
					int z=match[0][w];
					match[1][y]=w;
					match[0][w]=y;
					y=z;
				}
				break;
			}

			S[x]=T[y]=true;
			rep(v,n) if(slack(x,v)<slack(u_min[v],v)) u_min[v]=x;
		}
	}

	cost_t res=0;
	rep(u,n) res+=a[u][match[0][u]];
	return res;
}

int main(){
	int n; scanf("%d",&n);
	int W[100][100],E[100][100];
	rep(i,n) rep(j,n) scanf("%d",W[i]+j);
	rep(i,n) rep(j,n) scanf("%d",E[i]+j);

	char B[100][101];
	rep(i,n) scanf("%s",B[i]);

	int ans=0;
	rep(i,n) rep(j,n) if(B[i][j]=='o') ans+=E[i][j];

	int A[100][100];
	rep(i,n) rep(j,n) {
		if(B[i][j]=='o'){
			A[i][j]=-E[i][j];
		}
		else{
			A[i][j]=W[i][j];
		}
	}
	ans+=Kuhn_Munkres(n,A);

	bool kesanai[100][100]={};
	vector< pair<int,int> > ans_w,ans_e;
	rep(u,n){
		int v=match[0][u];
		if(B[u][v]=='.') ans_w.push_back(make_pair(u,v));
		else{
			kesanai[u][v]=true;
		}
	}
	rep(u,n) rep(v,n) if(B[u][v]=='o' && !kesanai[u][v]) ans_e.push_back(make_pair(u,v));

	printf("%d\n",ans);
	printf("%d\n",ans_w.size()+ans_e.size());
	rep(i,ans_w.size()) printf("%d %d write\n",ans_w[i].first+1,ans_w[i].second+1);
	rep(i,ans_e.size()) printf("%d %d erase\n",ans_e[i].first+1,ans_e[i].second+1);

	return 0;
}

Measured memory_bytes: 1232
import sys
#input = sys.stdin.buffer.readline


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

#import numpy as np

def main():
	n=II()
	if n%1000==0:
		print(0)
	else:
		print((n//1000)*1000+1000-n)


if __name__ == "__main__":
	main()


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

using namespace std;

int main()
{
    int N, K;
    cin >> N >> K;

    int h[N], dp[N];

    for(int i=0;i<N;i++)
    {
        cin >> h[i];
        dp[i]=1000000000;
    }
    dp[N-1]=0;
    dp[N-2]=abs(h[N-1]-h[N-2]);

    for(int i=N-3;i>=0;i--)
    {
        for(int j=i+1;j<min(N, i+K+1);j++)
        {
            dp[i]=min(dp[i], dp[j]+abs(h[j]-h[i]));
        }
    }
    cout << dp[0];
}


Measured memory_bytes: 4404