akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>


using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair
#define mt make_tuple

int main(void)
{
  int N;
  cin >> N;
  char c[N];
  int r_pos=-1, r_num=0;
  int w_pos=-1;
  for(int i=0;i<N;i++){
    cin >> c[i];
    if(c[i] == 'R'){
      r_pos=i;
      r_num++;
    }
    else if(c[i] == 'W')w_pos=i;
    // printf("%c, %d %d\n", c[i], r_pos, w_pos);
  }
  if(r_pos == -1 or w_pos == -1)printf("%d\n", 0);
  else{
    int cnt = 0;
    for(int i=r_num;i < N;i++){
      if(c[i] == 'R')cnt++;
    }
    printf("%d\n", cnt);
  }
  return 0;
}


Measured memory_bytes: 3868
import qualified Data.ByteString.Char8 as B
import Data.Maybe (fromJust)

main :: IO ()
main = do
    [n, y] <- map (fst . fromJust . B.readInt) . B.words <$> B.getLine
    let ans = [[a, b, n - a - b] | a <- [0..2000], b <- [0..2000], 9 * a + 4 * b == y `div` 1000 - n && n - a - b >= 0]
    if null ans
        then putStrLn "-1 -1 -1"
        else do
            let [a, b, c] = head ans
            putStrLn $ show a ++ " " ++ show b ++ " " ++ show c


Measured memory_bytes: 892
<?php
    //ユークリッドの互除法
    function gcd($a,$b){
        if($b === 0){
            return $a;
        }
        return gcd($b,$a%$b);
    }

    fscanf(STDIN,'%d',$n);

    //参考　⇒　https://note.com/tanon_cp/n/n2eb2bb1d69f9
    //keyがaとbの最大公約数でvalueがその個数になる
    $gcdAAndB = array_fill(1,$n,0);
    for ($a = 1; $a <= $n; ++$a) {
        for ($b = 1; $b <= $n; ++$b) {
            ++$gcdAAndB[gcd($a,$b)];
        }
    }
    //$gcdAAndBとkeyの最大公約数がvalue個ある
    $ans = 0;
    $count = count($gcdAAndB);
    for ($c = 1; $c <= $n; ++$c) {
        for ($index = 1; $index <= $count; ++$index) {
            $ans += gcd($c,$index) * $gcdAAndB[$index];
        }
    }
    echo $ans.PHP_EOL;

?>

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

int main() {
  int N;
  cin >> N;
  int ans = 0;
  int big = 0;
  vector<int> nn(N,0);
  for (int i=0; i<N; i++) {
    cin >> nn[i];
    big = max(big,nn[i]);
    if (nn[i] >= big) {
      ans++;
    }
  }
  
  cout << ans << endl;
}

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;
using P = pair<int,int>;
 
int main(){
    int n, in;
    cin >> n;
    vector<int> ans(n);
    rep(i, n) ans.at(i) = 1;
    rep(i, n-1){
        cin >> in;
        ans.at(in-1)++;
    }
    rep(i, n) cout << ans.at(i)-1 << endl;
    return 0;
}

Measured memory_bytes: 4052
N, M = map(int, input().split())
PYs = []
G = {}
for i in range(M):
  P, Y = map(int, input().split())
  PYs.append((P, Y))
  if not(P in G):
    G[P] = []
  G[P].append(Y)
D = {}
for P in G:
  L = sorted(G[P])
  d = {}
  for i in range(len(L)):
    Y = L[i]
    d[Y] = i
  D[P] = d
for P, Y in PYs:
  r = format(P, "0>6")+format(D[P][Y]+1, "0>6")
  print(r)



Measured memory_bytes: 70940
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
int main() {
    int n = 2;
    cin >> n;
    vector<ll> monster(n + 1, 0);
    vector<ll> hero(n + 1, 0);
    for(int i = 0; i < n + 1; ++i) {
        cin >> monster[i];
    }
    for(int i = 0; i < n; ++i) {
        cin >> hero[i];
    }
    
    ll defeat = 0;
    ll buffer = 0;
    for(int i = 0; i <= n; ++i) {
        if(monster[i] <= hero[i] + buffer) {
            defeat += monster[i];
            if(monster[i] <= buffer) {
                buffer = hero[i];
            } else if(monster[i] > buffer) {
                buffer = hero[i] + buffer - monster[i];
            }
        } else if(monster[i] > hero[i] + buffer) {
            defeat += hero[i] + buffer;
            buffer = 0;
        }
    }
    cout << defeat << endl;
    return 0;
}

Measured memory_bytes: 1792
n,m = gets.chomp.split(" ").map(&:to_i)

# 最大公約数をmax_mとすると a_1, a_2, ..., a_n はすべてmax_mで割り切れるので
# m = a_1 + a_2 + ... + a_n もmax_mで割り切れる

# 最大10^9ループ
(m / n).downto(1) do |i|
  if m % i == 0
    puts i
    exit
  end
end


Measured memory_bytes: 14188
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
const ll INF = 1LL<<60;
const ll MOD = 1e9+7;


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n; cin>>n;
    ll ans = 0;
    for(ll i=1; i*i<n; i++){
        ll m = (n-i)/i;
        if(n/m==n%m)ans+=(n-i)/i;
    }
    cout<<ans<<endl;
    return 0;
}

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

using namespace std;
//131073
const int maxn = 223456;
typedef pair<int, int> pii;
typedef long long ll;
multiset<int>s;
multiset<int>::iterator it;

int main(){
    ios_base::sync_with_stdio(0);
//    freopen("input.txt", "r", stdin);
    int a, b;
    cin >> a >> b;
    ll res = 0;

    if(a == 0) {
        if (b == 100)res = 101;
        else
            res = b;
    }
    else {

        if (b == 100)res = pow(100L, a) * 101;
        else res = pow(100L, a) * b;
    }
    cout << res << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
  int i, j, k, n, m, dx[8] = {1, 1, 1, 0, 0, -1, -1, -1}, dy[8] = {1, 0, -1, 1, -1, 1, 0, -1};
  scanf("%d%d", &m, &n);
  char s[m][n + 10];
  for(i = 0; i < m; ++i) scanf("%s", s[i]);
  for(i = 0; i < m; ++i) for(j = 0; j < n; ++j) {
    if(s[i][j] == 'x') {
      for(k = 0; k < 8; ++k) if(i + dy[k] >= 0 && i + dy[k] < m && j + dx[k] >= 0 && j + dx[k] < n && s[i + dy[k]][j + dx[k]] == '-') s[i + dy[k]][j + dx[k]] = 'a';
    }
    if(s[i][j] == 'o') {
      if(j != n - 1 && s[i][j + 1] == '-') s[i][j + 1] = 'a';
      if(j && s[i][j - 1] == '-') s[i][j - 1] = 'a';
    }
  }
  //for(i = 0; i < m; ++i) printf("%s\n", s[i]);
  int ans = 0;
  for(i = 1; i < m; ++i) for(j = 0; j < n; ++j) if(s[i][j] == '-') ++ans;
  printf("%d\n", ans);
  return 0;
}


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

using namespace std;
long long n,ans,nr,num;
int main()
{
    cin>>n;
    if(n%2==1)
    {
        cout<<0;
        return 0;
    }
    num=10;
    while(num<=n)
    {
        ans+=n/num;
        num*=5;
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		int t = scan.nextInt();
		int u = scan.nextInt();
		int n = t + 1;
		int m = u + 1;
		int[][] a = new int[n][m];
		int b[] = new int[m];
		int c[] = new int[n];
		int i,r;
		for(i = 0; i < n - 1; ++i){
			for(r = 0; r < m - 1; ++r){
				a[i][r] = scan.nextInt();
				a[i][m - 1] += a[i][r];
				a[n - 1][r]	+= a[i][r];
				a[n - 1][m - 1] += a[i][r];
			}
		}
		for(i = 0; i < n; ++i){
			for(r = 0; r < m; ++r){
				if(r == m - 1){
					System.out.println(a[i][r]);
				}
				else
				System.out.print(a[i][r]+" ");
				
			}
		}
	}
}
		

Measured memory_bytes: 42044
#include <bits/stdc++.h>
using namespace std;
int main(void){
  int a,b,c,x,count=0;
  cin >> a >> b >> c >> x;
 
  for(int i=0;i<=a;i++){
      for(int j=0;j<=b;j++){
          for(int k=0;k<=c;k++){
              if((500*i)+(100*j)+(50*k)==x){
                  count++;
              }
          }
      }
  }
  cout << count << endl;
    return 0;
    
}


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

int main()
{
	int N;
	string c;
	cin >> N >> c;

	int rcnt = 0;
	for( int i = 0; i < N; i++ ) {
		if( c[i] == 'R' ) rcnt++;
	}
	int ans = 0;
	for( int i = rcnt; i < N; i++ ) {
		if( c[i] == 'R' ) ans++;
	}

	cout << ans << endl;
}


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

int main(){
	int n;
  	cin >> n;
  	int a[n] = {};
   	for(int i = 0; i < n; i++){
    	cin >> a[i];
    }
   	
  	int x = 0;
  	for(int i = 0; i < n; i++){
    	x = x ^ a[i];
    }
  
  	for(int i = 0; i < n; i++){
    	a[i] = x ^ a[i];
    }
  	
  	for(int i = 0; i < n; i++){
    	cout << a[i] << " ";
    }
  	cout << endl;
}

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

// {U}{INT,LONG,LLONG}_{MAX,MIN}
#define ALPHABET    (26)
#define INF         INT_MAX
#define MOD         (1000000007LL)

using LL  = long long;
// }}}

int main() {
    std::ios::sync_with_stdio(false);
    string a, b, c;cin >> a >> b >> c;
    string ans = "YES";
    if(a[a.size()-1] != b[0]) ans = "NO";
    if(b[b.size()-1] != c[0]) ans = "NO";
    cout << ans << endl;
    return 0;
}


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

using namespace std;
using MatrixGraph = vector<vector<int>>;

const int no_edege = -1;
const int started_label = 1;
const int no_label = -1;
const int no_cost = -1;
const int max_weight = 2'000;

int total_weight(MatrixGraph matrix_graph, int started_label) {
  vector<int> min_weights(matrix_graph.size(), max_weight + 1);
  vector<int> visited(matrix_graph.size(), false);
  min_weights[started_label - 1] = 0;
  int weight_sum = 0;

  while(true) {
    int min_weight = max_weight + 1;
    int min_label = no_label;
    for(int i = 0; i < matrix_graph.size(); i++) {
      if(visited[i]) {
        continue;
      }
      if(min_weights[i] < min_weight) {
        min_weight = min_weights[i];
        min_label = i + 1;
      }
    }
    if(min_label == no_label) {
      break;
    }

    visited[min_label - 1] = true;
    weight_sum += min_weight;

    for(int i = 0; i < matrix_graph.size(); i++) {
      if(matrix_graph[min_label - 1][i] < min_weights[i]) {
        min_weights[i] = matrix_graph[min_label - 1][i];
      }
    }
  }

  return weight_sum;
}

int main() {
  int vertex_num;
  cin >> vertex_num;
  MatrixGraph matrix_graph(vertex_num, vector<int>(vertex_num, no_edege));

  // Init
  for(int i = 0; i < vertex_num; i++) {
    for(int j = 0 ;j < vertex_num; j++) {
      int weight;
      cin >> weight;
      if(weight == no_edege) {
        matrix_graph[i][j] = max_weight + 1;
        continue;
      }
      matrix_graph[i][j] = weight;
    }
  }

  cout << total_weight(matrix_graph, started_label) << endl;
}



Measured memory_bytes: 3240
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const long long INF = 1LL << 60;    // 1.15x10^18
using ll = long long;

ll ans = INF;
void rec(ll x2, ll x1, ll y2, ll y1, ll cnt) {
    if (cnt > ans) return ;
    ll all = x2 + x1;
    if (y2 * 2 + y1 <= all) return void(ans = min(ans, cnt));
    rec(
        max(0LL, y2 - all),
        y1 + min(all, y2) - max(0LL, all - y2),
        x2, x1, cnt + 1
    );
    rec(
        y2 - max(0LL, all - y1 + 1) / 2,
        max(0LL, y1 - all) + max(0LL, all - y1) % 2,
        x2, x1, cnt + 1
    );
}

int main() {
    ll n, m; cin >> n >> m;
    rec(n, 0, m, 0, 0);
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 3132
#include <iostream>
#include <string>
#include <queue>
#include <map>
using namespace std;

int main(){
	string s;
	while(1){
		map<string,bool> used;
		cin >> s;
		if(s == "0") break;
		queue<string> que;
		que.push(s);
		for(int i = 0;;i++){
			int siz = que.size();
			if(!siz){
				cout << "NA" << endl;
				break;
			}
			for(int j = 0;j < siz;j++){
				s = que.front();que.pop();
				if(used[s]) continue;
				used[s] = true;
				char c = s[0];
				bool flag = true;
				for(int k = 1;k < s.length();k++){
					if(s[k] != c) flag = false;
				}
				if(flag){
					cout << i << endl;
					goto end;
				}
				for(int k = 0;k < s.length() - 1;k++){
					if(s[k] != s[k + 1]){
						string t = s;
						if(s[k] != 'g' && s[k + 1] != 'g'){
							t[k] = 'g';
							t[k + 1] = 'g';
							que.push(t);
						}
						else if(s[k] != 'r' && s[k + 1] != 'r'){
							t[k] = 'r';
							t[k + 1] = 'r';
							que.push(t);
						}
						else{
							t[k] = 'b';
							t[k + 1] = 'b';
							que.push(t);
						}
					}
				}
			}
		}
		end:
		continue;
	}
	return 0;
}

Measured memory_bytes: 5184
#include <iostream>
#include <cstring>
#include <string>    
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
ll n, x, a, box, ans;

int main(){
	cin >> n >> x;
	
	cin >> box;
	ans = 0;
	for(ll i = 2; i <= n; i++){
		cin >> a;
		if(box+a <= x){box = a;}
		else{
			ans += box+a-x;
			box = max(x-box, 0LL);
		}
	}
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
class Main{
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    int k = sc.nextInt();
    long sum=0;
    for(int i=1;i<=k;i++){
      for(int j=1;j<=k;j++){
        for(int ij=1;ij<=k;ij++){
          sum+=gcd(gcd(i,j),ij);
        }
      }
    }
    pl(sum+"");
  }

  public static int gcd(int a,int b){
    if(a<b){
      int aa=a;a=b;b=aa;
    }
    while(a%b!=0){
      int c=a%b;
      a=b;b=c;
    }
    return b;
  }

  public static void pr(String str){
    System.out.print(str);
  }
  public static void pl(String str){
    System.out.println(str);
  }
}


Measured memory_bytes: 38860
S = input()

str_list = list('abcdefghijklmnopqrstuvwxyz')
str_cnt = [0 for i in range(len(str_list))]

for i in range(len(S)):
    s = S[i]
    
    index_s = str_list.index(s)
    str_cnt[index_s] += 1

if (0 not in str_cnt):
    ans = 'None'
else:
    ans = str_list[str_cnt.index(0)]

print(ans)


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

using namespace std;

int main() {
    int n, a[] = {9, 900, 90000};
    cin >> n;
    int cnt = 0, k = n;
    while (k) {
        k /= 10;
        cnt++;
    }
    int sum = 0;
    if (cnt % 2) {
        for (int i = 1; i < cnt; i += 2) {
            sum += a[(i - 1) / 2];
        }
        int x = pow(10, cnt - 1);
        sum += n - x + 1;
    } else {
        for (int i = 1; i < cnt; i += 2) {
            sum += a[(i - 1) / 2];
        }
    }
    cout<<sum<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define debug(x) cerr << "\n" \
                      << #x << " = " << x << ".\n"
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define print(xx) cout << (xx) << endl
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vint;
const int INF = ((1LL << 30) + (1LL << 29));
const ll MOD = 1000000007;

/* 
*/
//================== INPUT ========================
int N, Q;
vector<tuple<int, int, int>> R;
vector<int> D;
//=================================================
//=================================================
void input()
{
    cin >> N >> Q;
    R.resize(N);
    D.resize(Q);
    rep(i, N) cin >> get<0>(R[i]) >> get<1>(R[i]) >> get<2>(R[i]);
    rep(i, Q) cin >> D[i];
}
//=================================================
void solve()
{
    vector<pii> events;
    for (auto x : R)
    {
        events.push_back(make_pair(get<0>(x) - get<2>(x), get<2>(x)));
        events.push_back(make_pair(get<1>(x) - get<2>(x), -get<2>(x)));
    }
    sort(events.begin(), events.end());

    set<int> s;

    auto iter = events.begin();
    int i = 0;

    for (auto q : D)
    {
        for (; i < 2 * N; ++i)
        {
            if (events[i].first > q)
            {
                break;
            }
            int ev = events[i].second;
            if (ev > 0)
            {
                s.insert(ev);
            }
            else
            {
                s.erase(s.lower_bound(-ev));
            }
        }
        cout << ((s.empty()) ? (-1LL) : (*s.begin())) << endl;
    }
}

//=================================================
signed main()
{
    input();
    solve();
    return 0;
}

Measured memory_bytes: 23400
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define FOR(i,l,r) for(i=l;i<r;i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(x) x.begin(),x.end()
#define P pair<ll,ll>
#define F first
#define S second
signed main(){
  ll L,R,i,j,ans=2018;cin>>L>>R;
  if(R-L>=2018)ans=0;
  else FOR(i,L,R+1)FOR(j,L,i)ans=min(ans,i%2019*j%2019);
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-15
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int main(){
	ll N,M;
	scan(N);scan(M);
	vint yakusu;
	int yakucount[50000]={0};
	ll kari=M;
	for(int i=1;i<=sqrt(kari)+1;i++){
		if(kari%i==0){
			yakusu.push_back(i);
			yakusu.push_back(kari/i);
			//printf("i:%d kari:%lld\n",i,kari);
		}
	}
	ll ans=1;
	sort(yakusu.begin(),yakusu.end());
	int yakukosu=yakusu.size();
	//rep(i,yakukosu) printf("%d ",yakusu[i]);
	//kaigyo;
	rep(i,yakukosu){
		if(yakusu[i]>=N){
			ans=M/yakusu[i];
			break;
		}
	}
	prin(ans);
	return 0;
}


Measured memory_bytes: 256
const int LG = 21;
const int FN = 400005;
const long long MOD = 1e9 + 7;
const long long INF = 1e9;
const long long INFLL = 1e18;

#include <bits/stdc++.h>

using namespace std;

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

#define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define fi first
#define se second
#define re return
#define pb push_back
#define uniq(x) sort(all(x)); (x).resize(unique(all(x)) - (x).begin())

#ifdef LOCAL
#define dbg(x) cerr << __LINE__ << " " << #x << " " << x << endl
#define ln cerr << __LINE__ << endl
#else
#define dbg(x) void(0)
#define ln void(0)
#endif // LOCAL

int cx[4] = {-1, 0, 1, 0};
int cy[4] = {0, -1, 0, 1};
string Ans[2] = {"No", "Yes"};
string ANS[2] = {"NO", "YES"};

ll inq(ll x, ll y)
{
    if (!y) re 1 % MOD;
    ll l = inq(x, y / 2);
    if (y % 2) re l * l % MOD * x % MOD;
    re l * l % MOD;
}

ll rev(ll x)
{
    return inq(x, MOD - 2);
}

bool __precomputed_combinatorics = 0;
vector<ll> __fact, __ufact, __rev;

void __precompute_combinatorics()
{
    __precomputed_combinatorics = 1;
    __fact.resize(FN);
    __ufact.resize(FN);
    __rev.resize(FN);
    __rev[1] = 1;
    for (int i = 2; i < FN; i++) __rev[i] = MOD - __rev[MOD % i] * (MOD / i) % MOD;
    __fact[0] = 1, __ufact[0] = 1;
    for (int i = 1; i < FN; i++) __fact[i] = __fact[i - 1] * i % MOD, __ufact[i] = __ufact[i - 1] * __rev[i] % MOD;
}

ll fact(int x)
{
    if (!__precomputed_combinatorics) __precompute_combinatorics();
    return __fact[x];
}

ll cnk(int n, int k)
{
    if (k < 0 || k > n) return 0;
    if (!__precomputed_combinatorics) __precompute_combinatorics();
    return __fact[n] * __ufact[n - k] % MOD * __ufact[k] % MOD;
}

int Root(int x, vector<int> &root)
{
    if (x == root[x]) return x;
    return root[x] = Root(root[x], root);
}

void Merge(int v, int u, vector<int> &root, vector<int> &sz)
{
    v = Root(v, root), u = Root(u, root);
    if (v == u) return;
    if (sz[v] < sz[u])
    {
        sz[u] += sz[v];
        root[v] = u;
    }
    else
    {
        sz[v] += sz[u];
        root[u] = v;
    }
}

int ok(int x, int n)
{
    return 0 <= x && x < n;
}

void bfs(int v, vi &dist, vector<vi> &graph)
{
    fill(all(dist), -1);
    dist[v] = 0;
    vi q = {v};
    for (int i = 0; i < q.size(); i++)
    {
        for (auto u : graph[q[i]])
        {
            if (dist[u] == -1)
            {
                dist[u] = dist[q[i]] + 1;
                q.push_back(u);
            }
        }
    }
}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int a, b;
    cin >> a >> b;
    cout << 6 - a - b;
}

/* Note:
Check constants at the beginning of the code.
    N is set to 4e5 but be careful in problems with large constant factor.
    Setting N in every problem is more effective.
Check corner cases.
    N = 1
No def int long long for now.
Add something here.
*/


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<sstream>
using namespace  std;
vector<string> split(const string &s, char delimiter)
{
	vector<string> ret;
	size_t now = 0, find;
	while ((find = s.find_first_of(delimiter, now)) != string::npos)
	{
		ret.push_back(string(s, now, find - now));
		now = find + 1;
	}
	ret.push_back(string(s, now, s.size() - now));
	return ret;
}
int main()
{
	string s;
	int ave = 0;
	int sum = 0;
	int count = 0;
	while (cin >> s)
	{
		vector<string> line = split(s, ',');
		stringstream ss1;
		stringstream ss2;
		int a;
		int b;
		ss1 << line[0];
		ss1 >> a;
		ss2 << line[1];
		ss2 >> b;
		//cout << a << " " << b<<endl;
		sum += a * b;
		ave += b;
		count++;
	}
	cout << sum << endl;
	/*double a, b;
	a = (ave / count) - ave * 1.0 / count;
	if (a < 0)a = -a;
	b = ((int)(ave * 1.0 / count + 0.5)) - ave * 1.0 / count;
	if (b < 0)b = -b;
	if (a >= b )cout << (int)(ave * 1.0 / count + 0.5) << endl;
	else cout << (ave /count) << endl;*/
	cout << (int)(ave * 1.0 / count + 0.5) << endl;
	return 0;
}

Measured memory_bytes: 1232
r = int(input())
# ints = [int(input()) for _ in range(r)]

# maxv = None
# for i in range(len(ints)):
#   if i == len(ints)-1: break

#   if maxv is None:
#     maxv = max(ints[i+1:])-ints[i]
#   else:
#     maxv = max(maxv, max(ints[i+1:])-ints[i])
    
# print(maxv)

R = [int(input()) for _ in range(r)]

ans = R[1] - R[0]
prev = R[0]
for j in range(1, len(R)):
  cur = R[j]
  ans = max(ans, cur - prev)
  prev = min(cur, prev)

print(ans)


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

int main()
{
  int N; cin >> N;
  cout << (N+2-1)/2 << endl; 
}

Measured memory_bytes: 256
#include<iostream>
#include<string>

using namespace std;

#define ll long long
#define REPI(x) for(int i = 0; i < x; i++)
#define REPJ(x) for(int j = 0; j < x; j++)

ll int num = 0;
ll int ans = 0;
ll int a[5];

int main(void)
{
        int N; 
        cin >> N;

        char name[5]  = {'M', 'A', 'R', 'C', 'H'};
        char s[11];
        
        REPI(N)
        {       
                cin >> s;
                REPJ(5) 
                {
                        if (s[0] == name[j])
                        {
                                a[j]++;
                        }
                }
        }

        for (int i = 0; i < 5; i++){
                for (int j = i+1; j < 5; j++){
                        for (int k = j+1; k < 5; k++){
                                ans += a[i]*a[j]*a[k];
                        }
                }
        }
        cout << ans << endl;
        return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <cmath>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#define rep(i,n) for (int i=0;i<n;i++)
using ll = long long;
using namespace std;


void solve(){

}
int main (){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int a,b;
    cin >> a >> b;
    if((a*b)%2==0){
        cout << "Even";
    }
    else{
        cout << "Odd";
    }

    return 0;
}


Measured memory_bytes: 256
//ALDS1_9B
#include <iostream>
using namespace std;
#define MAX 2000000

int H,A[MAX+1];
void maxHeapify(int i){
 int l,r,largest;
 l=2*i;
 r=2*i+1;
 if(l<=H && A[l]>A[i]) largest=l;
 else largest=i;
 if(r<=H && A[r]>A[largest]) largest=r;
 if(largest!=i){
  swap(A[i],A[largest]);
  maxHeapify(largest);
 }
}

int main(){
 cin>>H;
 for(int i=1;i<=H;i++) cin>>A[i];
 for(int i=H/2;i>=1;i--) maxHeapify(i);
 for(int i=1;i<=H;i++) cout<<" "<<A[i];
 cout<<endl;
 return 0;
}

Measured memory_bytes: 3116
#include <stdio.h>
int main(){
    int a, b ,c, d, e, f;
    scanf("%d", &a);
    b= a/100;
    c= b*100;
    d= a-c;
    e= d%10;
    f= d/10;
    if (b==7){
        printf("Yes\n");
    }
    else if(e==7){
        printf("Yes\n");
    }
    else if(f==7){
        printf("Yes\n");
    }
    else{
        printf("No\n");
    }
    return 0;
}

Measured memory_bytes: 1664
#include<iostream>
#include<string>

using namespace std;

int main() {
    string S, T;

    cin >> S >> T;

    int ans = 0;

    for(int i = 0; i < S.length(); i++) {
        if(S[i] == T[i]) {
            ans++;
        }
    }

    cout << ans << endl;

    return 0;
}

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	vector<int> a(n);
	int xsum = 0;
	for (int &x : a) {
		cin >> x;
		xsum ^= x;
	}
	for (int i = 0; i < n; i++) {
		if (i > 0) {
			cout << ' ';
		}
		cout << (xsum ^ a[i]);
	}
	cout << '\n';
	return 0;
}


Measured memory_bytes: 3984
#include <bits/stdc++.h>
#define INF 2e9
#define MOD 1000000007
using namespace std;
typedef long long llong;
typedef long double ldouble;

using Graph = vector<vector<int>>;

// int ctoi(const char c){
//   if('0' <= c && c <= '9') return (c-'0');
//   return -1;
// }

// int gcd(int a, int b){
//   int ma = max(a,b);
//   int mi = min(a,b);
//   if(mi == 0) return ma;

//   return gcd(mi, ma%mi);
// }

int main(){
  llong X;
  cin >> X;
  llong five = 5;
  for(llong i=0; i<=120; ++i){
    for(llong j=0; j<=120; ++j){
      if((llong)(pow(i, five)-pow(j, five)) == X){
        cout << i << " " << j << endl;
        return 0;
      }else if((llong)(pow(i, five) + pow(j, five)) == X){
        cout << i << " " << -j << endl;
        return 0;
      }
    }
  }
}

Measured memory_bytes: 4060
#include <bits/stdc++.h>
using namespace std;
int count (string s) {
    for(int i = 0; i < (int)s.size(); i++)
    {
        if(!(s[i] == 'A' || s[i] == 'C' || s[i] == 'T' || s[i] == 'G')){
            return -1;
        }
    }
    return (int)s.size();
}
int main () {
    string s;
    cin >> s;
    int max =0;
    for(int i = 0; i < (int)s.size(); i++)
    {
        for(int j = i+1; j <= (int)s.size(); j++)
        {
            int tmp = count(s.substr(i,j-i));
            if(tmp > max) max = tmp;
        }
        
    }
    cout << max << endl;
    
}

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



int sc1() {int x; scanf("%d", &x); return x;}
long long sc2() {long long x; scanf("%lld", &x); return x;}

void out(int x) { printf("%d", x);}
void outnl(int x) { printf("%d\n", x);}
void outsps(int x){printf("%d ", x);}

#define  gcd(a,b)         __gcd(a,b)
#define  lcm(a,b)         (a*b)/gcd(a,b)
#define  Int              sc1()
#define  LL               sc2()
#define  For(n)           for(int i=0;i<n;i++)
#define  Forj(n)          for(int j=0;j<n;j++)
#define  Fork(n)          for(int k=0;k<n;k++)
#define  For1(n)          for(int i=1;i<=n;i++)
#define  ll               long long
#define  vi               std::vector<int>
#define  vll              std::vector<ll>
#define  qui              qu
#define  pb               push_back
#define  mpsi             std::map<string, int>
#define  nl               printf("\n");

const int mod           = 1e9 + 7;
const int inf           = (int)2e9 + 5;
const ll  Inf           = (ll)1e18 + 5;
const int N             = 2e6 + 5;

inline int add(int a, int b) {a += b; return a >= mod ? a - mod : a;}
inline int sub(int a, int b) {a -= b; return a < 0 ? a + mod : a;}
inline int mul(int a, int b) {return (ll)a * b % mod;}


 int vis[N];

 int a[N],b[N];

int solve() {

    string s;
    cin>>s;
    int n = s.size(),cnt=0;
    for(int i=0; i<n/2;i++)
    {
        if(s[i]!=s[n-1-i])
            {
                cnt++;
                //cout<<s[i]<<endl;
            }
    }
    outsps(cnt);
    nl;
}




int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int test = 1, tc = 0;
    //scanf("%d", &test); 
    //cin >> test;
    while (test--) {
        //printf("Case %d: ", ++tc);
        solve();
    }

    return 0;




}


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

using namespace std;
using ll = long long;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
	REP(i, v.size()) { if (i)os << " "; os << v[i]; }return os;
}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
	REP(i, v.size()) { if (i)os << endl; os << v[i]; }return os;
}

const ll INF = 1LL << 60;
ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

#define int long long

inline void my_io() {

	std::ios::sync_with_stdio(false);

	std::cin.tie(0);

	cout << fixed << setprecision(10);

}

signed main() {
	ll n, ans;
	double t, a, h;
	double now = 1000000.0;

	cin >> n >> t >> a;

	REP(i, n) {
		cin >> h;
		if (now > abs(t - h * 0.006 - a)) {
			now = abs(t - h * 0.006 - a);
			ans = i + 1;
		}
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
//#pragma GCC optimize ("-O3","unroll-loops")
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>


#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 FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define m0(x) memset(x,0,sizeof(x))
#define print(x) cout<<x<<'\n';
#define pe(x) cout<<x<<" ";
#define lb(v,n) lower_bound(v.begin(), v.end(), n);
#define ub(v,n) upper_bound(v.begin(), v.end(), n);
#define int long long
#define all(x) (x).begin(), (x).end()
//#define double long double

using namespace std;

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

const int MOD = 1e9 + 7;
const ll INF = 1e17;
const double pi = acos(-1);
const double EPS = 1e-10;
typedef pair<int, int>P;
const int MAX = 200020;

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

	int K, X; cin >> K >> X;
	FOR(i, X - K + 1, X + K) {
		pe(i);
	}cout << endl;
 }



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <cmath>
#include <vector>
#include <numeric>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>

using ll = unsigned long long int;
using ul = unsigned long long int;
const ll LL_MAX (1LL<<60);
const ll MOD (1000000007);

#define rep(i,s,e) for(ll i=(s); i<(e); i++) 

using namespace std;

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

    ll n, k;
    cin >> n >> k;

    ll y(0), cnt(0);
    for (ll i=0;n>0;i++)
    {
        ll z = n%k;
        y += z*pow(10,i);
        //cout << n << ' ' << k << endl;
        n = n/k;
        cnt++;
    }

    //cout << y << endl;
    //cout << to_string(y).size() << endl;
    cout << cnt << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef int LL;
typedef double dl;
#define opt operator
#define pb push_back
const LL maxn=1e5+9,mod=998244353,up=1e5;
LL Read(){
	LL x(0),f(1); char c=getchar();
	while(c<'0' || c>'9'){
		if(c=='-') f=-1; c=getchar();
	}
	while(c>='0' && c<='9'){
		x=(x<<3ll)+(x<<1ll)+c-'0'; c=getchar();
	}return x*f;
}
LL L,n,q;
LL a[1<<9][maxn],v[maxn<<3],w[maxn<<3];
void chkmax(LL &x,LL y){
	x=std::max(x,y);
}
LL Query(LL x,LL l){
	if(x<=L) return a[x][l];
	else{
		LL ret(Query(x/2,l));
		if(l>=w[x]) chkmax(ret,Query(x/2,l-w[x])+v[x]);
		return ret;
	}
}
int main(){
    n=Read(); L=(1<<9)-1;
    for(LL i=1;i<=n;++i){
    	v[i]=Read(); w[i]=Read();
	}
	for(LL i=1;i<=L;++i){
		LL f(i/2);
		for(LL j=1;j<=up;++j){
		    a[i][j]=a[f][j];
		    if(j>=w[i]) chkmax(a[i][j],a[f][j-w[i]]+v[i]);
		}
	}
	q=Read();
	while(q--){
		LL x(Read()),l(Read());
		printf("%d\n",Query(x,l));
	}
	return 0;
}


Measured memory_bytes: 205448
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>


using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e16;
const ll MOD = 1e9 + 7;

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




ll gcd(ll a, ll b){
    return b? gcd(b, a % b) : a;
}


int main() {
    ll n;
    cin >> n;
    ll ans;
    cin >> ans;
    REP(i, n - 1){
        ll a;
        cin >> a;
        ans = gcd(ans, a);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
<?php
$n = trim(fgets(STDIN));
$arr = explode(" ", trim(fgets(STDIN)));
$check = 0;
$sum = 0;

$total = array_sum($arr);
$t = $total / 2;

for($i=0; $i < $n; $i++){
    $check += $arr[$i];
    $arr_2[] = abs($t-$check);
}

$min = min($arr_2);
$key = array_keys($arr_2, min($arr_2));
for($i=0; $i<=$key[0]; $i++){
    $sum += $arr[$i];
}
$r = $total - $sum;
echo abs($r - $sum);
?>

Measured memory_bytes: 4728
S = input()

if S == "SUN":
  print(7)
elif S == "MON":
  print(6)
elif S == "TUE":
  print(5)
elif S == "WED":
  print(4)
elif S == "THU":
  print(3)
elif S == "FRI":
  print(2)
elif S == "SAT":
  print(1)

Measured memory_bytes: 2940
#include <iostream>
#include <cstring>

int main(){
	int count[26];
	char c;
	memset(count, 0, sizeof(int)*26);
	
	while(std::cin >> c){
		if('A' <= c && c <= 'Z')
			c -= 'A';
		else if('a' <= c && c <= 'z')
			c -= 'a';
		else
			continue;
		count[c]++;
	}
	
	for(int i=0; i<26; i++)
		std::cout << (char)(i + 'a') << " : " << count[i] << std::endl;
	
	return 0;
}

Measured memory_bytes: 1140
/* @ by batr (T) */
#include <bits/stdc++.h>
 
#define ll long long
#define pb push_back
#define mp make_pair
#define all(X) (X).begin(), (X).end()
 
#define cmp_all(X) (X).begin(), (X).end(), cmp
 
#define B begin()
#define E end()
#define sz size()
#define skip continue
 
#define ppi pair<pair<int, int>, int>
#define pii pair<int, int> 
#define pli pair<ll, int>
#define pcc pair<char, char>
 
#define F first
#define S second
 
using namespace std;
 
const int maxn = 1e7 + 17;
const int MAXN = maxn * 4;
const int darr = 1e3 + 17;
const ll INF = 1e17 + 5;
const int mod = 1e9 + 7;
 
void Need_For_Speed () {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}

int n, m;
char c[darr][darr];

int main () {
	Need_For_Speed();
	cin >> n >> m;
	for (int i = 0; i <= n + 1; i++) {
		for (int j = 0; j <= m + 1; j++) {
			c[i][j] = '.';
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> c[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (c[i][j] == '#' && c[i-1][j+1] == '#') {
				cout << "Impossible";
				return 0;
			}
		}
	}
	cout << "Possible";
	return 0;
}

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

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)
#define TRACE(x) cerr << #x << " = " << x << endl

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

const int mod = 1e9 + 7;

int add(int x, int y) {x += y; if(x >= mod) return x - mod; return x;}
int sub(int x, int y) {x -= y; if(x < 0) return x + mod; return x;}
int mul(int x, int y) {return (ll) x * y % mod;}

int n, k, s;

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

  cin >> n >> k >> s;
  REP(i, k)
    cout << s << " ";
  REP(i, n - k){
    if(s > 1e6)
      cout << 1 << " ";
    else
      cout << 10000000 << " ";
  }
}



Measured memory_bytes: 1280
N = gets.to_i
abcs = N.times.map { gets.split.map(&:to_i) }

dp = Array.new(N + 10) { Array.new(3, 0) }
N.times do |i|
  a, b, c = abcs[i]
  da, db, dc = dp[i]
  dp[i + 1] = [
    [db + a, dc + a].max,
    [da + b, dc + b].max,
    [da + c, db + c].max
  ]
end
puts dp[N].max

Measured memory_bytes: 25980
#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"

using namespace std;

using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i8 = int8_t;
using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;

constexpr char newl = '\n';
constexpr double eps = 1e-10;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define F0R(i,b) FOR(i,0,b)
#define RFO(i,a,b) for (int i = ((b)-1); i >=(a); i--)
#define RF0(i,b) RFO(i,0,b)
#define fi first
#define se second
#define debug(x) cout << #x << ": " << x << '\n';
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()

template<typename T1, typename T2> inline void chmin(T1& a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
template<class T> void Print(vector<T> v) {
  F0R(i, v.size()) {
    cout << v[i] << ' ';
  }
  cout << newl;
}

#if 1


// INSERT ABOVE HERE
signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int a;
  cin >> a;
  cout << (a + a * a + a * a * a);
}
#endif


Measured memory_bytes: 3608
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace MyProgram{
    public class Program
    {	
        static int cnt;
        static int n;
        static string target;
        public static void Main(string[] args)
    	{
    	    target = Console.ReadLine();
            n = int.Parse(target);
            
            string ss = "";
            DFS(ss);
            
            Console.WriteLine(cnt);
    	}
    	
    	public static void DFS(string s)
    	{
    	    if(s.Length > target.Length) return;
    	    if(s.Length >= 3)
    	    {
    	        if(s.Contains("7") &&s.Contains("5") && s.Contains("3")){
        	        int x = int.Parse(s);
        	        if(n >= x) cnt++;
    	        }
    	    }
    	    DFS(s+"7");
    	    DFS(s+"5");
    	    DFS(s+"3");
    	}
    }
}

Measured memory_bytes: 13140
N, M = [int(c) for c in input().split()]
a = [int(input()) for _ in range(M)]+[-1]
j=0

dp = [0, 1]

for i in range(N):
    if i+1 == a[j]:
        dp.append(0)
        while i+1==a[j]:
            j+=1
    else:
        dp.append((dp[i]+dp[i+1]) % 1000000007)

print(dp[-1])

Measured memory_bytes: 7824
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define f first
#define s second
#define mp make_pair
int main()
{
	int n;
	cin>>n;
	int arr[n][3];
	for(int i=0;i<n;i++)
	cin>>arr[i][0]>>arr[i][1]>>arr[i][2];
	int dp[n][3];
	dp[0][0]=arr[0][0];
	dp[0][1]=arr[0][1];
	dp[0][2]=arr[0][2];
	for(int i=1;i<n;i++)
	{
		dp[i][0]=max(dp[i-1][1],dp[i-1][2])+arr[i][0];
		dp[i][1]=max(dp[i-1][0],dp[i-1][2])+arr[i][1];
		dp[i][2]=max(dp[i-1][1],dp[i-1][0])+arr[i][2];
	}
	cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]));
	return 0;
}
  


Measured memory_bytes: 2560
#include<cstdio>
#include<queue>
#include<tuple>

using namespace std;

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

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

int main(){
	int h, w; scanf("%d %d", &h, &w);
	char s[50][51];
	rep(i, h) scanf("%s", s[i]);
	int b = 0;
	rep(i, h) rep(j, w){
		if(s[i][j] == '#') b++;
	}
	queue<tuple<int, int, int>> q;
	q.push(make_tuple(0, 0, 0));
	bool flag[50][50] = {};
	flag[0][0] = 1;
	int res = -1;
	while(!q.empty()){
		int x, y, t;
		tie(y, x, t) = q.front(); q.pop();
		if(y == h - 1 && x == w - 1){ res = t; break; }
		rep(i, 4){
			int ny = y + dy[i], nx = x + dx[i];
			if(ny < 0 || ny >= h || nx < 0 || nx >= w || flag[ny][nx] || s[ny][nx] == '#') continue;
			q.push(make_tuple(ny, nx, t + 1));
			flag[ny][nx] = 1;
		}
	}
	if(res == -1) puts("-1");
	else printf("%d\n", h * w - b - res - 1);
	return 0;
}

Measured memory_bytes: 256
//  Volume11-1127
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        int n=scan.nextInt();
        int m=scan.nextInt();
        int[][] matrixa=new int[n][m];
        int[] matrixb=new int[m];
        int outPint;
        
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                matrixa[i][j]=scan.nextInt();
            }
        }
        for(int j=0; j<m; j++){
            matrixb[j]=scan.nextInt();
        }
        for(int i=0; i<n; i++){
            outPint=0;
            for(int j=0; j<m; j++){
                outPint+=matrixa[i][j]*matrixb[j];
            }
            System.out.println(outPint);
        }
    }
}


Measured memory_bytes: 40784
#include<bits/stdc++.h>
using namespace std;
using ll = long long ;
ll const inf = 1e18;
int const nax = 3e5 + 10;

struct P {
    long long cost;
    int nod;
    int res;

    P () {}
    P (long long cost, int nod, int res) : cost(cost), nod (nod), res(res) {}

    bool operator < (const P &x) const {
        return cost > x.cost;
    }
};

struct edge {
    int to;
    int cost;
    int times;
};

bool vis1[55];
int n, m, s;
vector<edge> a[55];
long long dist[55];
long long dp[55][2505];


void run_dijkstar () {
    priority_queue<pair <int, int> , vector< pair < int, int> >, greater< pair< int, int> > > q;
    fill(dist + 1, dist + 1 + n, LLONG_MAX);
    dist[1] = 0;
    q.push(make_pair(0, 1));

    while (!q.empty()) {
        auto x = q.top();
        q.pop();
        if (vis1[x.second]) continue;
        vis1[x.second] = true;

        for (auto i : a[x.second]) {
            if (!vis1[i.to] && dist[i.to] > x.first + i.times) {
                dist[i.to] = x.first + i.times;
                q.push(make_pair(dist[i.to], i.to));
            }
        }
    }

    for (int i = 2 ; i <= n ; ++ i) {
        printf("%lld\n", dist[i]);
    }
    exit(0);
}
bool vis[55][2505];

int c[55], d[55];

int main ()  {

    scanf("%d %d %d", &n, &m, &s);

    for (int i = 1 ; i <= m;  ++ i) {
        int u, v, a, b;
        scanf("%d %d %d %d", &u, &v, &a, &b);
        ::a[u].push_back({v, a, b});
        ::a[v].push_back({u, a, b});
    }

    for (int i = 1 ; i <= n ; ++ i) {
        scanf("%d %d", c + i, d + i);
    }

    fprintf(stderr, "ANS\n");

    if (s > n * n) {
        run_dijkstar();
    }

    for (int i = 1 ; i <= n ; ++ i) {
        for (int j = 0 ; j <= 2500 ; ++ j) {
            dp[i][j] = inf;
        }
    }

    dp[1][s] = 0;

    priority_queue<P> q;
    q.push({0, 1, s});

    while (!q.empty()) {
        auto x = q.top();
        q.pop();

        if (vis[x.nod][x.res]) continue;
        vis[x.nod][x.res] = true;

        int to = min(x.res + c[x.nod], 2500);

        if (!vis[x.nod][to] && dp[x.nod][to] > dp[x.nod][x.res] + d[x.nod]) {
            dp[x.nod][to] = dp[x.nod][x.res] + d[x.nod];
            q.emplace(dp[x.nod][to], x.nod, to);
        }

        for (auto i : a[x.nod]) {
            if (x.res >= i.cost && dp[x.nod][x.res] + i.times < dp[i.to][x.res - i.cost]) {
                if (!vis[i.to][x.res - i.cost]) {
                    dp[i.to][x.res - i.cost] = dp[x.nod][x.res] + i.times;
                    q.emplace(dp[i.to][x.res - i.cost], i.to, x.res - i.cost);
                }
            }
        }
    }

    for (int i = 2 ; i <= n;  ++ i) {
        long long res = inf;

        for (int j = 0 ; j <= 2500 ; ++ j) {
            res = min(res, dp[i][j]);
        }

        printf("%lld\n", res);
    }


}
/*
    Good Luck
        -Lucina
*/


Measured memory_bytes: 6316
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
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;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

int main() {
    ll n;
    cin >> n;
    vector<int> ans;
    while (n != 0) {
        if (n % 2 == 0) {
            ans.push_back(0);
            n /= -2;
        } else {
            ans.push_back(1);
            n = (n - 1) / -2;
        }
    }
    while (sz(ans) > 0 && ans.back() == 0) ans.pop_back();
    if (sz(ans) == 0) ans.push_back(0);
    reverse(all(ans));
    for (int x : ans) cout << x;
    cout << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
    
using namespace std;
    
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef unsigned long long ull;
#define RI(x) scanf("%d",&x)
#define RII(x,y) scanf("%d%d",&x,&y)
#define RIII(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define DRI(x) int x;RI(x)
#define DRII(x,y) int x,y;RII(x,y)
#define DRIII(x,y,z) int x,y,z;RIII(x,y,z)
#define PI(x) printf("%d\n",x)
#define PIS(x) printf("%d ",x)
#define sf scanf
#define pf printf
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(a) a.begin(),a.end()
#define min3(a,b,c) min(a, min(b,c))
#define max3(a,b,c) max(a, max(b,c))
#define sz(a) ((int)a.size())
#define clr(x,a) memset(x, a, sizeof x)
#define REP(i,n) for(int i=0; i<n; ++i)
#define rep(i,a,b) for(int i=a; i<b; ++i)
#define repp(i,a,b) for(int i=a ; i>=b ; --i)
const ll MAX = 2500000000;
const int inf=0x3f3f3f3f;
const double EPS = 1e-9;
const double PII = 2*asin(1.0);
const ll mod=1e9+7;
//const ll mod=1000000039261LL;
//const ll mod2=1000000018417LL;
//const ll mod=1300031;
/*
freopen(TASK".in","r",stdin);	
freopen(TASK".out","w",stdout);
*/
int double_cmp(double x, double y = 0, double tol = EPS){return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;}

int vetor[200];

int main()
{
	DRI(n);
	
	REP(i, 2*n)RI(vetor[i]);
	
	sort(vetor, vetor+n+n);
	
	int res=0;
	
	for(int i=n+n-2 ; i>=0 ; i-=2)res+=vetor[i];
	
	PI(res);
}

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

int main()
{
	int n;

	while( cin >> n ){
		for( int i = 0; i < n; ++i ){
			int h, m;
			char dummy;
			cin >> h >> dummy >> m;

			int hAngle = h * 300 + m * 10 / 2;
			int mAngle = m * 10 * 360 / 60;
			int angle = hAngle > mAngle ? hAngle - mAngle : mAngle - hAngle;
			string message;
			if( ( angle < 300 && angle >= 0 ) || ( angle <= 3600 && angle > 3300 ) ){
				message = "alert";
			}else if( ( angle >= 900 && angle <= 2700 ) ){
				message = "safe";
			}else{
				message = "warning";
			}

			cout << message << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 1188