akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<set>
#include<map>
using namespace std;

#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define ROF(i,b,a) for (int i=(b);i>(a);--i)
#define REP(i,n) FOR(i,0,n)
#define PER(i,n) ROF(i,n-1,-1)

typedef int i32;
typedef long long int i64;
typedef unsigned long long int ui64;
typedef float f32;
typedef double f64;
typedef long double f128;
typedef pair<int,int> Pi;

constexpr int INF = 1e9 + 7;
constexpr int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};

int main() {
    int a,b,c,d,e,f; cin>>a>>b>>c>>d>>e>>f;
    int water=0,sugar=0;
    int answ=100,anss=0;
    REP(i,31) {
        REP(j,31) {
            water = 100*(a*i+b*j);
            int res = f-water;
            if (res<=0) break;
            res = min(res,water*e/100);
            REP(k,res+1) {
                REP(l,res+1) {
                    sugar = c*k+d*l;
                    if (sugar>res) break;
                    if (sugar*(answ+anss)>=(water+sugar)*anss) answ=water,anss=sugar;
                }
            }
        }
    }
    cout<<answ+anss<<" "<<anss<<endl;
}


Measured memory_bytes: 256
function Main(input) {
  input = input.trim()
  input = input.split("\n");
  var N =input[0];
  var arr = input[1].split(" ").map(Number);
  var sum=0
  for(var i=0;i<N;i++){
    sum += 1/arr[i];
  }
  console.log(1/sum);
}Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

using ll = long long;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = numeric_limits<int>::max();
constexpr ll L_INF = numeric_limits<ll>::max();

//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

void solve() {
    ll N, K;
    cin >> N >> K;
    Vl A(N);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
    }
    sort(A.begin(), A.end());
    ll ans = 0;
    for (ll i = 0; i < K; i++) {
        ans += A[i];
    }
    cout << ans << "\n";
}

//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

int main() {
#ifdef FASTIO
    cin.tie(0), cout.tie(0);
    ios::sync_with_stdio(false);
#endif
#ifdef FILEINPUT
    ifstream ifs("./in_out/input.txt");
    cin.rdbuf(ifs.rdbuf());
#endif
#ifdef FILEOUTPUT
    ofstream ofs("./in_out/output.txt");
    cout.rdbuf(ofs.rdbuf());
#endif
    solve();
    cout << flush;
    return 0;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  int N, M;
  cin >> N >> M;
  vector<pair<int,int>> AB(N), CD(M);
  for(int i = 0; i < N; i++) {
    int a, b;
    cin >> a >> b;
    AB[i] = {a, b};
  }
  for(int j = 0; j < M; j++) {
    int c, d;
    cin >> c >> d;
    CD[j] = {c, d};
  }
  for(int i = 0; i < N; i++) {
  	int ans = -1, dist = 1 << 30;
    for(int j = 0; j < M; j++) {
      int d = abs(CD[j].first - AB[i].first) + abs(CD[j].second - AB[i].second);
      if (dist > d) {
      	dist = d;
        ans = j;
      }  
    }
    cout << ans + 1 << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <iomanip> 
#include <cstring>
#include <queue>
#include <stack> 
#include <vector>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
int k,a,b;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> k >> a >> b;
	for(int i = a;i <= b;i++){
		if(i % k == 0){
			cout << "OK" << endl;
			return 0;
		}
	}
	cout << "NG" << endl;
	return 0;
}

Measured memory_bytes: 3116
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric, std.container;

long P = 10^^9+7;
long[1001] F, RF;

long pow(long x, long n) {
    long y = 1;
    while (n) {
        if (n%2 == 1) y = (y * x) % P;
        x = x^^2 % P;
        n /= 2;
    }
    return y;
}

long inv(long x)
{
    return pow(x, P-2);
}

void init()
{
    F[0] = F[1] = 1;
    foreach (i, ref x; F[2..$]) x = (F[i+1] * (i+2)) % P;

    {
        RF[$-1] = 1;
        auto x = F[$-1];
        auto k = P-2;
        while (k) {
            if (k%2 == 1) RF[$-1] = (RF[$-1] * x) % P;
            x = x^^2 % P;
            k /= 2;
        }
    }
    foreach_reverse(i, ref x; RF[0..$-1]) x = (RF[i+1] * (i+1)) % P;
}

long comb(N)(N n, N k)
{
    if (k > n) return 0;
    auto n_b = F[n];    // n!
    auto nk_b = RF[n-k]; // 1 / (n-k)!
    auto k_b = RF[k];    // 1 / k!

    auto nk_b_k_b = (nk_b * k_b) % P; // 1 / (n-k)!k!

    return (n_b * nk_b_k_b) % P;  // n! / (n-k)!k!
}

long perm(N)(N n, N k)
{
    if (k > n) return 0;
    auto n_b = F[n];
    auto n_k_b = RF[n-k];
    return (n_b * n_k_b) % P;
}

void main()
{
    init();
    auto nk = readln.split.to!(long[]);
    auto N = nk[0];
    auto K = nk[1];
    auto DP = new long[][](N+1, K+1);
    DP[1][1] = 1;
    foreach (n; 2..N+1) {
        foreach (k; 1..K+1) {
            DP[n][k] = (DP[n-1][k-1] + k * DP[n-1][k] % P) % P;
        }
    }
    writeln(DP[N][K]);
}


Measured memory_bytes: 10304
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <fstream>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 10e15+9
#define MOD 1000000007
#define EPS 1e-10
#define MAX_N 100100
#define MAX_M 100100

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;
typedef pair<P, char> PC;

int N, M, r, q;

int t, n, m, s, ts, te;

int atime[1010][10010];
bool used[1010][10010];

int main(){
	while (cin >> N >> M&&N + M){
		REP(i, 1010){
			REP(j, 10010){
				atime[i][j] = 0;
				used[i][j] = 0;
			}
		}
		cin >> r;
		REP(i, r){
			cin >> t >> n >> m >> s;
			t -= 540;
			if (s == 1){
				atime[n][m] = t;
			}
			else{
				FOR(j, atime[n][m], t){
					used[j][m] = 1;
				}
			}
		}
		cin >> q;
		REP(i, q){
			int ans = 0, t = -1;
			cin >> ts >> te >> m;
			ts -= 540;
			te -= 540;
			FOR(j, ts, te + 1){
				if (t == -1){
					if (used[j][m])t = j;
				}
				else{
					if (!used[j][m]){
						//cout << "!" << endl;
						//cout << j - 1 << " " << t << endl;
						ans += j - t;
						t = -1;
					}
				}
			}
			if (t != -1){
				ans += te - t;
			}
			cout << ans << endl;
		}
	}
}

Measured memory_bytes: 50524
N, M = map(int, input().split())
memo = [{'ac': 0, 'wa': 0, 'ok': False} for i in range(N)]

for i in range(M):
  p, s = input().split()
  p = int(p)-1
  if not memo[p]['ok']:
    if s == 'WA':
      memo[p]['wa'] += 1
    else:
      memo[p]['ac'] += 1
      memo[p]['ok'] = True

ac = 0
wa = 0
for i in memo:
  if i['ok']:
    ac += 1
    wa += i['wa']
    
print(ac, wa)
    
    

Measured memory_bytes: 33524
import java.util.ArrayDeque
import kotlin.Comparator
import kotlin.String

fun main(args: Array<String>) {
    val (h, w) = readIntList()
    val (ch, cw) = readIntList().map { it - 1 }
    val (dh, dw) = readIntList().map { it - 1 }
    val s = List(h) { readString() }

    val q = ArrayDeque<Pair<Int, Int>>()
    q.addLast(ch to cw)

    val ans = List(h) { MutableList(w) { Int.MAX_VALUE } }
    ans[ch][cw] = 0

    val af = listOf(Pair(0, 1), Pair(0, -1), Pair(1, 0), Pair(-1, 0))

    while (q.isNotEmpty()) {
        val (x, y) = q.removeFirst()

        af.forEach { (xf, yf) ->
            val tx = x + xf
            val ty = y + yf
            if (tx >= 0 && ty >= 0 && tx < h && ty < w && s[tx][ty] == '.' && ans[x][y] < ans[tx][ty]) {
                ans[tx][ty] = ans[x][y]
                q.addFirst(tx to ty)
            }
        }

        for (xf in -2..2) {
            for (yf in -2..2) {
                val tx = x + xf
                val ty = y + yf
                if (tx >= 0 && ty >= 0 && tx < h && ty < w && s[tx][ty] == '.' && ans[x][y] + 1 < ans[tx][ty]) {
                    ans[tx][ty] = ans[x][y] + 1
                    q.addLast(tx to ty)
                }
            }

        }
    }

    if (ans[dh][dw] == Int.MAX_VALUE) {
        println(-1)
    } else {
        println(ans[dh][dw])
    }
}

// read
fun readString() = readLine()!!
fun readInt() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readStringList() = readLine()!!.split(" ")
fun readIntList() = readLine()!!.split(" ").map(String::toInt)
fun readLongList() = readLine()!!.split(" ").map(String::toLong)

Measured memory_bytes: 90632
"""
Segment-Tree
    maxval:入力されるデータ以上の値
    offset:根と枝の数(n=1のときは根1つ葉2つの木)
    init_array(array):配列で初期化
    update(k,x):k番目をxに変更
    sum_query(p,q):[p,q)の範囲の合計
"""
class SegmentTree():
    maxval=(1<<31)-1

    def __init__(self,n):
        self.offset=self.setOffset(n)
        self.segTree=[(0,self.maxval) for i in range(2*self.offset+1)]
        self.time=0

    def setOffset(self,n):
        if n==1:
            return 1
        else:
            return 2**(n-1).bit_length()-1

    def find(self,k):
        k+=self.offset
        data=self.segTree[k]
        while k:
            k=(k-1)//2
            data=max(data,self.segTree[k])
        return data

    def update_query(self,p,q,x):
        if p>=q:
            return

        self.time+=1
        p+=self.offset
        q+=self.offset-1
        v=(self.time,x)

        while q-p>1:
            #p%2==0
            if not p&1:
                self.segTree[p]=v
            #q%2==1
            if q&1:
                self.segTree[q]=v
                q-=1
            p=p//2
            q=(q-1)//2

        if p==q:
            self.segTree[p]=v
        else:
            self.segTree[p]=v
            self.segTree[q]=v

    def show(self):
        print(self.segTree)

n,q=map(int,input().split())
ST=SegmentTree(n)
for i in range(q):
    qry=list(map(int,input().split()))
    if qry[0]==0:
        ST.update_query(qry[1],qry[2]+1,qry[3])
    else:
        print(ST.find(qry[1])[1])



Measured memory_bytes: 26472
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
typedef long long ll;
int main(){
    int x; cin >> x;
    int a = x / 100;
    int b = x % 100;
    if(b > 5*a) cout << "0" << endl;
    else cout << "1" << endl;
}

Measured memory_bytes: 256
s = input()
r = 0
if s == 'SUN':
    r = 7
elif s == 'MON':
    r = 6
elif s == 'TUE':
    r = 5
elif s == 'WED':
    r = 4
elif s == 'THU':
    r = 3
elif s == 'FRI':
    r = 2
elif s == 'SAT':
    r = 1
print(r)

Measured memory_bytes: 38384
#include <bits/stdc++.h>
#define err(args...) {}
#ifdef DEBUG
#include "_debug.cpp"
#endif
using namespace std;
using ll = long long;
using ld = long double;
template <typename T> using lim = numeric_limits<T>;
template <typename T> istream& operator>>(istream& is, vector<T>& a) { for(T& x : a) { is >> x; } return is; }
template <typename T> struct grid : public vector<vector<T>> {
    int n, m;
    grid(int n, int m) : vector<vector<T>>(n, vector<T>(m)), n(n), m(m) {}
    grid(int n, int m, T zero) : vector<vector<T>>(n, vector<T>(m, zero)), n(n), m(m) {}
    grid(const grid& a) : vector<vector<T>>(a), n(a.n), m(a.m) {}
};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    grid<int> h(n, 3);
    for(int i = 0; i < n; i++) {
        for(int x = 0; x < 3; x++) {
            cin >> h[i][x];
        }
    }
    grid<int> opt(n, 3);
    for(int i = n - 1; i >= 0; i--) {
        for(int x = 0; x < 3; x++) {
            if(i == n - 1) {
                opt[i][x] = h[i][x];
            } else {
                for(int y = 0; y < 3; y++) {
                    if(y != x) {
                        opt[i][x] = max(opt[i][x], opt[i + 1][y] + h[i][x]);
                    }
                }
            }
        }
    }
    cout << max({opt[0][0], opt[0][1], opt[0][2]}) << endl;
    return 0;
}


Measured memory_bytes: 11264
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

struct vec
{
  double x, y;
  vec (const double& x0 = 0, const double& y0 = 0) : x(x0), y(y0) {}
  vec operator + (const vec& t) const {return vec(x+t.x, y+t.y);}
  vec operator - (const vec& t) const {return vec(x-t.x, y-t.y);}
  vec operator * (const double& t) const {return vec(x*t, y*t);}
  vec operator / (const double& t) const {return vec(x/t, y/t);}
  const double len2 () const {return x*x + y*y;}
  const double len () const {return sqrt(len2());}
  vec norm() const {return *this/len();}
  vec rotate_90_c () {return vec(y, -x);}
};

double dot(const vec& a, const vec& b) {return a.x*b.x + a.y*b.y;}
double crs(const vec& a, const vec& b) {return a.x*b.y - a.y*b.x;}

vec lin_lin_int(const vec& p0, const vec& v0, const vec& p1, const vec& v1)
{
  double t = crs(p1-p0, v1) / crs(v0, v1);
  return p0 + v0 * t;
}

vec circle(const vec& a, const vec& b, const vec& c)
{
  return lin_lin_int((a+b)/2, (b-a).rotate_90_c(), (a+c)/2, (c-a).rotate_90_c());
}

int n;
vec pot[100005];

int main()
{
  scanf("%d", &n);
  for(int i=1; i<=n; i++) scanf("%lf%lf", &pot[i].x, &pot[i].y);
  random_shuffle(pot+1, pot+n+1);
  vec o;
  double r2 = 0;
  for(int i=1; i<=n; i++)
    {
      if((pot[i]-o).len2() > r2)
        {
          o = pot[i], r2 = 0;
          for(int j=1; j<i; j++)
            {
              if((pot[j]-o).len2() > r2)
                {
                  o = (pot[i]+pot[j])/2, r2 = (pot[j]-o).len2();
                  for(int k=1; k<j; k++)
                    {
                      if((pot[k]-o).len2() > r2)
                        {
                          o = circle(pot[i], pot[j], pot[k]), r2 = (pot[k]-o).len2();
                        }
                    }
                }
            }
        }
    }
  printf("%.10lf\n", sqrt(r2));
  return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <iostream>
#include <cstdio>
#include <sstream>

#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>

#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;

int main(){
	int n, m, k, a, cont1 = 0, cont2 = 0, r, i;
	cin >> n >> m >> k;
	int s1, s2;
	vector<long long> x(200005);
	vector<long long> y(200005);
	
	for(i = 1; i <= n; i++){
		cin >> x[i];
	}
	for(i = 1; i <= m; i++){
		cin >> y[i];
	}
	s1 = s2 = 0;
	for(i = 1; i <= n; i++){
		if(s1+x[i] > k) break;
		cont1++;
		s1+=x[i];
		
	}
	for(i = 1; i <= m; i++){
		if(s1+s2+y[i] > k) break;
		cont2++;
		s2+=y[i];
	}
	
	r = cont1 + cont2;
	
	while(cont1 > 0){
		s1-=x[cont1--];
		while(s1 + s2 + y[cont2+1] <= k && cont2 < m){
            cont2++;
            s2 += y[cont2];
        }
        r = max(r, cont1 + cont2);
	}
	
	cout << r << endl;
	
	return 0;
}


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

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 ll INF=1LL << 60;

int main(){

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

    chmin(dp[i], dp[i-1]+abs(h[i-1]-h[i]));
    chmin(dp[i], dp[i-2]+abs(h[i-2]-h[i]));
    
  }
  
  cout<<dp[N-1]<<endl;

}



Measured memory_bytes: 1408
import collections

N = int(input())
D = list(map(int, input().split()))
mod = 998244353

if(D[0] != 0):
    print(0)
else:
    c = collections.Counter(D)
    ans = 1
    for val in D[1:]:
        ans = (ans*c[val-1])%mod
    print(ans)

Measured memory_bytes: 19936
#include <stdio.h>

int main(void){
	char in[5];
	scanf("%s", in);
	char a = in[0];
	char b = 0;
	for(int i = 0; i < 4; i++){
		if(a != in[i]){
			b = in[i];
			break;
		}
	}
	if(b == 0){
		printf("No\n");
		return 0;
	}
	int c1 = 0, c2 = 0;
	for(int i = 0; i < 4; i++){
		if(a == in[i])c1++;
		if(b == in[i])c2++;
	}
	if(c1 == 2 && c2 == 2)
		printf("Yes\n");
	else
		printf("No\n");
	return 0;
}


Measured memory_bytes: 128
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    enum { TREE = 1, JUMP = 2 };
    int x, y;
    while (cin >> x >> y, x) {
        vector<vector<int>> field(y, vector<int>(x));
        for (auto &v: field) for (int &vi: v) cin >> vi;
        vector<vector<int>> dp(y + 1, vector<int>(x, 0));
        for (int j = 0; j < x; j++) dp[0][j] = field[0][j] == 0;
        for (int i = 0; i < y - 1; i++) for (int j = 0; j < x; j++) {
            for (int k: {-1, 0, 1}) if (j + k >= 0 && j + k < x) {
                int ni = i + 1, nj = j + k;
                if (k == 0) {
                    if (field[i][j] == JUMP) ni++;
                } else {
                    if (field[i][j] == JUMP || field[ni][nj] == JUMP) continue;
                }
                if (ni < y && field[ni][nj] == TREE) continue;
                dp[ni][nj] += dp[i][j];
            }
        }
        int ans = 0;
        for (int j = 0; j < x; j++) ans += dp[y - 1][j] + dp[y][j];
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 3056
// eddy1021
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef double D;
typedef long double LD;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
#define mod9 1000000009LL
#define mod7 1000000007LL
#define INF  1023456789LL
#define INF16 10000000000000000LL
#define eps 1e-9
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#ifndef ONLINE_JUDGE
#define debug(...) printf(__VA_ARGS__)
#else 
#define debug(...)
#endif
inline LL getint(){
  LL _x=0,_tmp=1; char _tc=getchar();    
  while( (_tc<'0'||_tc>'9')&&_tc!='-' ) _tc=getchar();
  if( _tc == '-' ) _tc=getchar() , _tmp = -1;
  while(_tc>='0'&&_tc<='9') _x*=10,_x+=(_tc-'0'),_tc=getchar();
  return _x*_tmp;
}
inline LL add( LL _x , LL _y , LL _mod = mod7 ){
  _x += _y;
  return _x >= _mod ? _x - _mod : _x;
}
inline LL sub( LL _x , LL _y , LL _mod = mod7 ){
  _x -= _y;
  return _x < 0 ? _x + _mod : _x;
}
inline LL mul( LL _x , LL _y , LL _mod = mod7 ){
  _x *= _y;
  return _x >= _mod ? _x % _mod : _x;
}
LL mypow( LL _a , LL _x , LL _mod ){
  if( _x == 0 ) return 1LL;
  LL _ret = mypow( mul( _a , _a , _mod ) , _x >> 1 , _mod );
  if( _x & 1 ) _ret = mul( _ret , _a , _mod );
  return _ret;
}
LL mymul( LL _a , LL _x , LL _mod ){
  if( _x == 0 ) return 0LL;
  LL _ret = mymul( add( _a , _a , _mod ) , _x >> 1 , _mod );
  if( _x & 1 ) _ret = add( _ret , _a , _mod );
  return _ret;
}
inline bool equal( D _x ,  D _y ){
  return _x > _y - eps && _x < _y + eps;
}
void sleep( double sec = 1021 ){
  clock_t s = clock();
  while( clock() - s < CLOCKS_PER_SEC * sec );
}
#define Bye exit(0)
int __ = 1 , _cs;
/*********default*********/
void build(){

}
#define N 60
int n , a[ N ] , mx;
void init(){
  n = getint();
  for( int i = 1 ; i <= n ; i ++ )
    a[ i ] = getint();
  mx = 1;
  for( int i = 2 ; i <= n ; i ++ )
    if( abs( a[ i ] ) > abs( a[ mx ] ) )
      mx = i;
}
vector< pair<int,int> > ans;
void solve(){
  if( a[ mx ] < 0 ){
    for( int i = 1 ; i <= n ; i ++ )
      if( i != mx )
        ans.push_back( { mx , i } );
    for( int i = n ; i > 1 ; i -- )
      ans.push_back( { i , i - 1 } );
  }else{
    for( int i = 1 ; i <= n ; i ++ )
      if( i != mx )
        ans.push_back( { mx , i } );
    for( int i = 1 ; i < n ; i ++ )
      ans.push_back( { i , i + 1 } );
  }
  printf( "%d\n" , (int)ans.size() );
  for( auto x : ans )
    printf( "%d %d\n" , x.first , x.second );
}
int main(){
  build();
  //__ = getint();
  while( __ -- ){
    init();
    solve();
  }
}


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

int main() {
    vector<vector<int>> a(3, vector<int>(3));
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> a[i][j];
        }
    }
    int n;
    cin >> n;
    map<int, bool> m;
    for (int i = 0; i < n; i++) {
        int t;
        cin >> t;
        m[t] = true;
    }
    // 縦
    for (int i = 0; i < 3; i++) {
        if (m[a[i][0]] && m[a[i][1]] && m[a[i][2]]) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    // 縦
    for (int i = 0; i < 3; i++) {
        if (m[a[0][i]] && m[a[1][i]] && m[a[2][i]]) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    if (m[a[0][0]] && m[a[1][1]] && m[a[2][2]]) {
        cout << "Yes" << endl;
        return 0;
    }
    if (m[a[0][2]] && m[a[1][1]] && m[a[2][0]]) {
        cout << "Yes" << endl;
        return 0;
    }
    cout << "No" << endl;
}

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

vector<vector<ll>> V;
ll MOD = 1000000007;
ll mod(ll x){
    return (x%MOD + MOD)%MOD;
}

vector<ll> dfs(ll x,vector<bool>& vis){
    vis[x] = true;
    ll p =1,q = 1;
    for(ll k=0;k<V[x].size();k++){
        if(vis[V[x][k]] == false){
            vector<ll> T = dfs(V[x][k],vis);
            q = mod(q*T[0]);
            p = mod(p*mod(T[0]+T[1]));
        }
    }
    vector<ll> Z(2);
    Z[0] = p;
    Z[1] = q;
    return Z;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin>>n;
    V.resize(n+1);
    for(ll i=0;i<n-1;i++){
        ll x,y;
        cin>>x>>y;
        V[x].push_back(y);
        V[y].push_back(x);
    }
    vector<bool> vis(n+1,false);
    vector<ll> T = dfs(1,vis);
    cout<<mod(T[0]+T[1])<<endl;
}

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

using namespace std;

#define fastio ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;


int main()
{
	#ifndef ONLINE_JUDGE 
	freopen("input.txt", "r", stdin); 
	freopen("output.txt", "w", stdout); 
	#endif	
	
	fastio;

	int n;
	cin >> n;
	ll arr[n], sum = 0, prod = 0, mod = 1000000007;

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

	for(int i = 0; i < n; i++)
	{
		prod = prod % mod + ((arr[i] % mod * ((sum - arr[i]) % mod)) % mod) % mod;
		sum -= arr[i];
	}

	cout << prod;
	return 0;

}

Measured memory_bytes: 5212
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <memory>
#include <string>

#include <algorithm>
#include <complex>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>

using namespace std;

#ifdef _MSC_VER
#define __typeof__ decltype
#endif

#define ITER(c)         __typeof__((c).begin())
#define FOREACH(it, c)  for (ITER(c) it=(c).begin(); it != (c).end(); ++it)
#define RITER(c)        __typeof__((c).rbegin())
#define RFOREACH(it, c) for (RITER(c) it=(c).rbegin(); it != (c).rend(); ++it)
#define REP(i, n)       REPEAT(i, 0, n)
#define REPEAT(i, k, n) for (int i = (k); i < (n); ++i)
#define REVREP(i, n)    for (int i = ((n)-1); i >= 0; --i)
#define FIND(c, n)      std::find((c).begin(), (c).end(), (n));
#define BSEARCH(c, n)   std::binary_search((c).begin(), (c).end(), (n))
#define LLPOW(p1,p2)    ((ll)pow((double)(p1), (int)p2))
#define ESIZEOF(A)      (sizeof(A)/sizeof((A)[0]))
#define MIN(p1,p2)      (((p1)<(p2))?(p1):(p2))
#define MAX(p1,p2)      (((p1)>(p2))?(p1):(p2))
#define CIN_NO_SYNC     do { cin.tie(0); ios_base::sync_with_stdio(false); } while(0)
#define GETSTR(p)       fgets((p), sizeof(p), stdin)
#define CHOMP(p)        do{ char *_q = (p) + strlen(p)-1; if(*_q == '\n') *_q = 0; } while(0)

int main(){

    string s;
    getline(cin, s);
    FOREACH(it, s){
        if(isalpha(*it)){
            *it = toupper(*it);
        }
    }
    cout << s << endl;
    return 0;
}

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

using namespace std;

int main() {
    int N;  // スイッチの個数
    int M;  // 電球の個数

    cin >> N >> M;

    vector<int> k(M, 0);       // 電球iのスイッチの個数
    vector<vector<int>> s(M);  // 電球iのスイッチの番号

    for (int i = 0; i < M; i++) {
        int k;
        cin >> k;
        for (int j = 0; j < k; ++j) {
            int tmp;
            cin >> tmp;
            tmp--;  // スイッチを0から数えるために、1つ引く
            s.at(i).push_back(tmp);
        }
    }

    vector<int> p(M, 0);  // 電球iのonになっているスイッチの個数を2で割った余り

    for (int i = 0; i < M; i++) {
        cin >> p.at(i);
    }

    vector<int> switches(N, 0);

    int allBulbFlashCount = 0;
    for (int i = 0; i < (1 << N); i++) {
        int bulbFlashCount = 0;
        for (int j = 0; j < M; j++) {
            int onFlagCount = 0;
            for (int k = 0; k < s.at(j).size(); k++) {
                if (i & (1 << s.at(j).at(k))) {
                    onFlagCount++;
                }
            }
            if (onFlagCount % 2 == p.at(j)) {
                bulbFlashCount++;
            }
        }
        if (bulbFlashCount == M) {
            allBulbFlashCount++;
        }
    }

    cout << allBulbFlashCount << endl;
}

Measured memory_bytes: 256
#encoding: utf-8

$map = []
$depth = [-1] * 100
$vis = [false] * 100

def build_map
  $n = gets.rstrip.to_i
  $map = []
  $n.times { $map << [0] * $n}
  (1..$n).each do |node|
    arr = gets.rstrip.split(/\s/).map(&:to_i)
    u, k = arr[0], arr[1]
    node = arr[2..-1]
    node.each { |v| $map[u - 1][v - 1] = 1}
  end
end

def bfs(x)
  $depth[x] = 0
  que = [x]
  $vis[x] = true
  while not que.empty?
    u, que = que.first, que.drop(1)
    $map[u].each_with_index do |node, idx|
      if node == 1 and not $vis[idx]
        $depth[idx] = $depth[u] + 1
        $vis[idx] = true
        que << idx
      end
    end
  end
end

def solve
  build_map
  bfs(0)
end

solve

(0..$n - 1).each do |node|
  puts "#{node + 1} #{$depth[node]}"
end

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

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

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

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


void solve(long long N, long long M,string S){
  reverse(S.begin(),S.end());
  vector<ll> dp(N+1,-1);
  dp[0]=0;
  ll l=0;
  for(ll i=1;i<=N;++i){
    if(S[i]=='1'){
      continue;
    }
    if(l==0||i-dp[l-1]>M){
      if(i-dp[l]>M){
        cout<<-1<<endl;
        return;
      }
      dp[l+1]=i;
      ++l;
    }else{
      dp[l]=i;
    }
  }
  vector<ll> ans;
  REP(l){
    ans.push_back(dp[i+1]-dp[i]);
  }
  reverse(ans.begin(),ans.end());
  REP(ans.size()){
    cout<<ans[i];
    if(i==ans.size()-1){
      cout<<endl;
    }else{
      cout<<" ";
    }
  }
}

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


Measured memory_bytes: 2424
import java.util.*;

public class Main {
  static int n;
  static long[] d;
  static ArrayList[] e;
  static HashMap[] elen;
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();
    d = new long[n];
    e = new ArrayList[n];
    elen = new HashMap[n];
    for(int i = 0; i < n; i++) {
      ArrayList<Integer> list = new ArrayList<Integer>();
      e[i] = list;
      HashMap<Integer, Long> map = new HashMap<Integer, Long>();
      elen[i] = map;
    }
    for(int i = 0; i < n - 1; i++) {
      int u = sc.nextInt() - 1;
      int v = sc.nextInt() - 1;
      long w = sc.nextLong();
      
      ArrayList<Integer> list = e[u];
      ArrayList<Integer> list2 = e[v];
      HashMap<Integer, Long> map = elen[u];
      HashMap<Integer, Long> map2 = elen[v];
      
      list.add(v);
      list2.add(u);
      map.put(v, w);
      map2.put(u, w);
 
      e[u] = list;
      e[v] = list2;
      elen[u] = map;
      elen[v] = map2;
    }
    dfs(0, -1);
    for(int i = 0; i < n; i++) {
      if((d[i] % 2) == 0) {
        System.out.println(0);
      } else {
        System.out.println(1);
      }
    }
  }

  public static void dfs(int v, int p) {
    ArrayList<Integer> list = e[v];
    HashMap<Integer, Long> map = elen[v];
    for(int i = 0; i < list.size(); i++) {
      int u = list.get(i);
      if(u != p) {
        long dd = map.get(u);
        d[u] = d[v] + dd;
        dfs(u, v);
      }
    }
  }
}

Measured memory_bytes: 140692
use std::io::prelude::*;

fn input<T: std::str::FromStr>() -> T {
    let stdin = std::io::stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}

fn main() {
    let n: usize = input();
    let xyd: Vec<(i32, i32, String)> = (0..n).map(|_| (input(), input(), input())).collect();
    const INF: i32 = std::i32::MAX;

    let mut xmin = vec![INF; 3];
    let mut xmax = vec![-INF; 3];
    let mut ymin = vec![INF; 3];
    let mut ymax = vec![-INF; 3];
    for (x, y, d) in xyd {
        if d == "R" {
            xmin[2] = std::cmp::min(xmin[2], x);
            xmax[2] = std::cmp::max(xmax[2], x);
            ymin[1] = std::cmp::min(ymin[1], y);
            ymax[1] = std::cmp::max(ymax[1], y);
        } else if d == "L" {
            xmin[0] = std::cmp::min(xmin[0], x);
            xmax[0] = std::cmp::max(xmax[0], x);
            ymin[1] = std::cmp::min(ymin[1], y);
            ymax[1] = std::cmp::max(ymax[1], y);
        } else if d == "U" {
            xmin[1] = std::cmp::min(xmin[1], x);
            xmax[1] = std::cmp::max(xmax[1], x);
            ymin[2] = std::cmp::min(ymin[2], y);
            ymax[2] = std::cmp::max(ymax[2], y);
        } else {
            xmin[1] = std::cmp::min(xmin[1], x);
            xmax[1] = std::cmp::max(xmax[1], x);
            ymin[0] = std::cmp::min(ymin[0], y);
            ymax[0] = std::cmp::max(ymax[0], y);
        }
    }

    let mut t = vec![0.0];
    for i in 0..3 {
        for j in i..3 {
            if xmin[i] != INF && xmin[j] != INF && xmin[i] - xmin[j] > 0 {
                t.push((xmin[i] - xmin[j]) as f64 / (j - i) as f64);
            }
            if xmax[i] != -INF && xmax[j] != -INF && xmax[i] - xmax[j] > 0 {
                t.push((xmax[i] - xmax[j]) as f64 / (j - i) as f64);
            }
            if ymin[i] != INF && ymin[j] != INF && ymin[i] - ymin[j] > 0 {
                t.push((ymin[i] - ymin[j]) as f64 / (j - i) as f64);
            }
            if ymax[i] != -INF && ymax[j] != -INF && ymax[i] - ymax[j] > 0 {
                t.push((ymax[i] - ymax[j]) as f64 / (j - i) as f64);
            }
        }
    }

    let mut ans = std::f64::MAX;
    for t in t {
        let mut xl = INF as f64;
        let mut xr = -INF as f64;
        let mut yl = INF as f64;
        let mut yr = -INF as f64;

        for i in 0..3 {
            if xmin[i] != INF {
                xl = f64::min(xl, xmin[i] as f64 + (i as i32 - 1) as f64 * t);
            }
            if xmax[i] != -INF {
                xr = f64::max(xr, xmax[i] as f64 + (i as i32 - 1) as f64 * t);
            }
            if ymin[i] != INF {
                yl = f64::min(yl, ymin[i] as f64 + (i as i32 - 1) as f64 * t);
            }
            if ymax[i] != -INF {
                yr = f64::max(yr, ymax[i] as f64 + (i as i32 - 1) as f64 * t);
            }
        }

        ans = f64::min(ans, (xr - xl) * (yr - yl));
    }

    println!("{}", ans);
}


Measured memory_bytes: 8444
#include<bits/stdc++.h>
using namespace std;
long long i=0,k,n;
int main()
{
	cin>>k;
	while(i<1000000)
	{
		i++;
		n=(n*10+7)%k;
		if(n==0)
		{
			cout<<i;
			return 0;
		}
	}
	cout<<-1;
	return 0;
}

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

int main(void) {
  string s;
  cin >> s;
  int cnt = 0;
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == 'o') cnt++;
  }
  cout << 700 + cnt * 100 << endl;
  return 0;
}

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

struct Benri { Benri() { std::cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(12);}} benri;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vll = vector<long long>;
using pll = pair<ll, ll>;
using ull = unsigned long long;

template <typename T> using PQ = priority_queue<T>;
template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define mp make_pair
#define F first
#define S second

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

constexpr long long MOD = 1000000007;
//constexpr long long MOD = 998244353;
constexpr int INF = 1001001001;
//constexpr ll INF = 1001001001001001001ll;
constexpr double EPS = 1e-10;
using number = long long;



int main() {
    int N; cin >> N;
    if (N & 1) {
        cout << (double)(N + 1) / (2.0 * (double)N) << endl;
    }
    else {
        cout << 0.5 << endl;
    }


}

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

int main() {
	int q, x;
	char com[20];
	list<int>v;
	scanf("%d", &q);
	for (int i = 0;i < q;i++) {
		scanf("%s",com);
		if (com[0] == 'i') {
			scanf("%d", &x);
			v.push_front(x);
		}
		else if (com[6] == 'L') {
			v.pop_back();
		}else if(com[6]=='F'){
			v.pop_front();
		}
		else if (com[0] == 'd') {
			scanf("%d", &x);
			for (list<int>::iterator it = v.begin();it != v.end();it++) {
				if (*it == x) {
					v.erase(it);
					break;
				}
			}
		}
	}
	int i = 0;
	for (list<int>::iterator it = v.begin();it != v.end();it++) {
		if (i++)printf(" ");
		printf("%d", *it);
	}
	printf("\n");
	return 0;
}


Measured memory_bytes: 34024
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main(){
	int n;
	cin>>n;
	ll dp[n];
	ll a[n];
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	dp[0]=0;
	dp[1]=abs(a[1]-a[0]);
	for(int i=2;i<n;i++){
		dp[i]=min(dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i]-a[i-2]));
	}
	cout<<dp[n-1];
	return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
using P = pair<int, int>;
#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: 5008
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;	cin >> n;
  long long ans=0;
  for(int i=1;i<=n;i++){
    if(i%3==0&&i%5==0)	continue;
    if(i%3==0)	continue;
    if(i%5==0)	continue;
    ans+=i;
  }
  cout << ans;
}

Measured memory_bytes: 3600
n,m,q=io.read("*n","*n","*n")

sum={}
for i=0,n do
	sum[i]={}
	for j=0,n do
		sum[i][j]=0
	end
end

for i=1,m do
	l,r=io.read("*n","*n")
	sum[l][r]=sum[l][r]+1
end

for i=0,n do
	for j=1,n do
		sum[i][j]=sum[i][j-1]+sum[i][j]
	end
end

for i=0,n do
	for j=1,n do
		sum[j][i]=sum[j-1][i]+sum[j][i]
	end
end

for i=1,q do
	l,r=io.read("*n","*n")
	print(sum[r][r]-sum[l-1][r]-sum[r][l-1]+sum[l-1][l-1])
end

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

using namespace std;

using ll = long long;

template<typename T> using V = std::vector<T>;
using Vi = V<int>;
using VVi = V<V<int>>;
using Vl = V<ll>;
using VVl = V<V<ll>>;
using Vs = V<string>;

template<typename T1, typename T2> using P = std::pair<T1, T2>;
using Pii = P<int, int>;
using Pll = P<ll, ll>;
using Pdd = P<double, double>;

template<typename T1, typename T2> using M = std::map<T1, T2>;
using Mii = M<int, int>;
using Msi = M<string, int>;

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REP2(i,s,e) for(int i=(int)(s);i<(int)(e);++i)
#define RREP(i,s,e) for(int i=(int)(s);i>=(int)(e);--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin(),ie=(c).end();i!=ie;++i)
#define ALL(c) (c).begin(), (c).end()

const double PI = acos(-1);
const ll MOD = 1e9+7;

struct UFTree {
    static const int MAX_N = 1e6;
    int p[MAX_N], r[MAX_N];

    UFTree(int n) : p(), r() {
        for(int i = 0; i < n; ++i) {
            p[i] = i;
            r[i] = 0;
        }
    }

    int root(int x) {
        return p[x] == x ? x : (p[x] = root(p[x]));
    }

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

    void unite(int x, int y) {
        x = root(x);
        y = root(y);
        if(x == y) return;

        if(r[x] < r[y]) {
            p[x] = y;
        } else {
            p[y] = x;
            if(r[x] == r[y]) r[x]++;
        }
    }
};

int n, q;
string s;

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

    UFTree t = UFTree(n);
    REP(i, q) {
        int c, x, y; cin >> c >> x >> y;
        if (c == 0) {
            t.unite(x, y);
        } else {
            std::cout << (t.same(x, y) ? 1 : 0) << '\n';
        }
    }

    return 0;
}



Measured memory_bytes: 10976
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef long long ll;

#define INF 10e17 // 4倍しても(4回足しても)long longを溢れない
#define rep(i,n) for(int i=0; i<n; i++)
#define rep_r(i,n,m) for(int i=m; i<n; i++)
#define END cout << endl
#define MOD 1000000007
#define pb push_back
#define sorti(x) sort(x.begin(), x.end())
#define sortd(x) sort(x.begin(), x.end(), std::greater<int>())
#define debug(x) std::cerr << (x) << std::endl;
#define roll(x) for (auto itr : x) { debug(itr); }

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

  ll n;
  cin >> n;
  vector<ll> a(n);
  vector<vector<ll> > dp(n + 1, vector<ll>(2));
  dp[0][0] = 0;
  dp[0][1] = -INF;

  rep(i,n) cin >> a[i];

  int cursor;
  ll d1, d2;
  for (int i = 1; i <= n; ++i) {
    cursor = i - 1;
    d1 = dp[cursor][0];
    d2 = dp[cursor][1];
    dp[i][0] = max(dp[cursor][0] + a[cursor], dp[cursor][1] - a[cursor]);
    dp[i][1] = max(dp[cursor][0] - a[cursor], dp[cursor][1] + a[cursor]);
  }

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


Measured memory_bytes: 6528
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <map>
#include <algorithm>
#include <string>
#include <utility>
#include <set>
#include <stack>
#include <deque>
#include <ctime>
#include <random>
#include <cassert>
#include <cmath>
#include <climits>
#include <queue>
#include <cstring>
#include <bitset>
#include <iomanip>
#include <chrono>

/*
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("popcnt")
#pragma GCC target("avx2")
*/


#ifdef LOCAL
    #define dbg(x) cout << #x << " : " << x << endl;
#else 
    #define dbg(x)
#endif

#define int long long
#define pb push_back
#define ppb pop_back()
#define mp make_pair
#define fi(a,b) for (int i=a;i<b;i++)
#define fj(a,b) for (int j=a;j<b;j++)
#define fk(a,b) for (int k=a;k<b;k++)
#define fi1(a,b) for (int i=a-1;i>=b;i--)
#define fj1(a,b) for (int j=a-1;j>=b;j--)
#define fk1(a,b) for (int k=a-1;k>=b;k--)
#define fx(x,a) for (auto& x : a)
#define rep(i, a, b) for (int i = a; i < b; ++i)
#define rep1(i, a, b) for (int i = a - 1; i >= b; --i)
#define siz(x) (int)x.size()
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;

template<typename T1, typename T2>inline void mine(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void maxe(T1 &x, T2 y) { if (x < y) x = y; }

ostream& operator << (ostream &a, const vector<int> &b) {
    for (auto k : b) cout << k << ' ';
    return a;
}


typedef long long ll;
typedef unsigned long long ull;
typedef char ch;
typedef string str;
typedef pair<int, int> pii;
typedef map<int, int> mii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<ch> vch;
typedef vector<vch> vvch;
typedef vector<str> vs;



const int MOD = 1000000007;
const int INF = 1000000050;
const long long BIG = (long long)2e18 + 50;
const int MX = 200010;
const double EPS = 1e-9;


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int a[MX];
int r[MX];
int l[MX];
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
       
    int n;
    cin >> n;
    vi st;
    fi(0, n) {
        cin >> a[i];
        while (st.size() && a[st.back()] > a[i]) {
            r[st.back()] = i;
            st.ppb;

        }
        st.pb(i);
    }     
    fx(x, st)
        r[x] = n;
    st.clear();
    fi1(n, 0) {
        while (st.size() && a[st.back()] > a[i]) {
            l[st.back()] = i;
            st.ppb;
        }
        st.pb(i);
    } 
    fx(x, st)
        l[x] = -1;
    int ans = 0;
    fi(0, n) 
        ans += a[i] * (r[i] - i) * (i - l[i]);
    cout << ans << '\n';
}

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

using namespace std;

int main(){

	int N;
	cin >> N;
	
	int t[N];
	int x[N];
	int y[N];
	
	for(int i=0;i<N;i++){
		cin >> t[i] >> x[i] >>y[i];
	}
	
	//時刻0の(0,0)からt[0]のx[0],y[0]に行けるかどうか
	//動ける回数はt[0]-0回
	//x[0]-0+y[0]-0回の移動は必要
	//t[0]-0>x[0]-0+y[0]-0かつ残りが2の倍数なら良い
	
	//bool ans = true;
	int temp_t=0;
	int temp_x = 0;
	int temp_y = 0;
	
	
	for(int i=0;i<N;i++){
		int move_t = t[i]-temp_t;
		int move = abs(x[i]-temp_x)+abs(y[i]-temp_y);
		bool b1 = move_t >= move;
		bool b2 = (move_t-move)%2==0;
		if(b1 && b2){
			temp_t = t[i];
			temp_x = x[i];
			temp_y = y[i];
		}
		else{
			cout << "No" <<endl;
			return 0;
		}
		
		
	}
	
	cout << "Yes" <<endl;

	return 0;

}

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

int main(){
  int n;
  cin >> n;
  
  if (n%10==2||n%10==4||n%10==5||n%10==7||n%10==9) cout << "hon" << endl;
  if (n%10==0||n%10==1||n%10==6||n%10==8) cout << "pon" << endl;
  if (n%10==3) cout << "bon" << endl;
}

Measured memory_bytes: 3624
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef char GRID;

#define WHITE '.'
#define BLACK '#'
#define EMPTY 0

int main()
{
	int H, W;
	cin >> H >> W;

	vector<vector<GRID>> grid(H, vector<GRID>(W));

	for (int Hi = 0; Hi < H; Hi++)
	{
		for (int Wi = 0; Wi < W; Wi++)
		{
			cin >> grid.at(Hi).at(Wi);
		}
	}

	for (int Hi = 0; Hi < H; Hi++)
	{
		int AmountOfWhite;	AmountOfWhite = 0;
		for (int Wi = 0; Wi < W; Wi++)
		{
			if (grid.at(Hi).at(Wi) == WHITE) AmountOfWhite++;
		}

		if (AmountOfWhite == W)
		{
			for (int Wi = 0; Wi < W; Wi++)
			{
				grid.at(Hi).at(Wi) = EMPTY;
			}
		}
	}
	
	for (int Wi = 0; Wi < W; Wi++)
	{
		int AmountOfWhite; AmountOfWhite = 0;
		for (int Hi = 0; Hi < H; Hi++)
		{
			if ((grid.at(Hi).at(Wi) == WHITE) || (grid.at(Hi).at(Wi) == EMPTY)) AmountOfWhite++;
		}

		if (AmountOfWhite == H)
		{
			for (int Hi = 0; Hi < H; Hi++)
			{
				grid.at(Hi).at(Wi) = EMPTY;
			}
		}
	}

	bool doPrint;
	for (int Hi = 0; Hi < H; Hi++)
	{
		doPrint = false;
		for (int Wi = 0; Wi < W; Wi++)
		{
			if (!(grid.at(Hi).at(Wi) == EMPTY))
			{
				cout << grid.at(Hi).at(Wi);
				doPrint = true;
			}
		}
		if (doPrint == true) cout << endl;
	}

	return 0;
}

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

#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

using namespace std;

#define debug(x) cout<<(#x)<<"="<<(x)<<", ";
#define debug1(x) debug(x) cout<<'\n';
#define debug2(x1, x2) debug(x1) debug(x2) cout<<'\n';
#define debug3(x1, x2, x3) debug(x1) debug(x2) debug(x3) cout<<'\n';
#define debug4(x1, x2, x3, x4) debug(x1) debug(x2) debug(x3) debug(x4) cout<<'\n';
#define debug5(x1, x2, x3, x4, x5) debug(x1) debug(x2) debug(x3) debug(x4) debug(x5) cout<<'\n';

#define fcout cout<<fixed<<setprecision(15)
#define repp(i,j,k) for(int i=j; i<k; ++i)
#define rep(i,j) repp(i,0,j)
#define rrep(i,j,k) for(int i=j; i>=k; --i)
#define all(x) (x).begin(), (x).end()
#define sort(x) sort(x.begin(), x.end())
#define lb(x,val) lower_bound(x.begin(), x.end(), val)
#define ub(x,val) upper_bound(x.begin(), x.end(), val)
#define pb(x) emplace_back(x);

typedef long long int lli;
typedef pair<int,int> pii;
typedef pair<lli,lli> pll;
typedef vector<int> vi;
typedef vector<lli> vl;
typedef tuple<int, int, lli> tiil;

//const lli M=998244353ll;
const lli M=1000000007ll;
const double D=1.0;

int main(){
	fast_io
	int a,b,c,d; cin>>a>>b>>c>>d;
	cout<<(min(a,b)+min(c,d));
	return 0;
}

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

int main(){
  int N;
  cin >> N;
  vector<string> W(N);
  for(int i=0;i<N;i++){
    cin >> W.at(i);
    if(i>0){
      if(W.at(i-1).at(W.at(i-1).size()-1) != W.at(i).at(0)){
        cout << "No" << endl;
        return 0;
      }
    }
  }
  for(int i=0;i<N-1;i++){
    for(int j=i+1;j<N;j++){
      if(W.at(i) == W.at(j)){
        cout << "No" << endl;
        return 0;
      }
    }
  }
  cout << "Yes" << endl;
}

Measured memory_bytes: 256
H, W = map(int, input().split())
pic = [input() for i in range(H)]

for i in range(W+2):
  print('#', end = "")
print()
for i in range(H):
  print('#', end = "")
  for j in range(W):
    print(pic[i][j], end = "")
  print('#')
for i in range(W+2):
  print('#', end = "")

Measured memory_bytes: 42344
#include "bits/stdc++.h"
using namespace std;
#define long int64_t

struct Solver {
	Solver() {
		ios::sync_with_stdio( false );
	}

	void solve() {
		int N, K;
		cin >> N >> K;

		int amax = 0;
		vector<int> A( N );
		for( auto& v: A ) {
			cin >> v;
			amax = max( amax, v );
		}

		int g = A[0];
		for( int i = 1; i < N; ++i ) { g = gcd( g, A[i] ); }

		if( K%g == 0 && K <= amax ) {
			cout << "POSSIBLE" << endl;
		}
		else {
			cout << "IMPOSSIBLE" << endl;
		}
	}

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

int main() {
	Solver().solve();
	return 0;
}


Measured memory_bytes: 640
def main():
    height, width = map(int, input().split(" "))
    grids = ["." * (width + 2)]
    for _ in range(height):
        grids.append("." + input() + ".")
    grids.append("." * (width + 2))
    is_possible = True
    for i in range(1, height + 1):
        for j in range(1, width + 1):
            if grids[i][j] == "#":
                if not (grids[i + 1][j] == "#" or grids[i - 1][j] == "#" or grids[i][j + 1] == "#" or grids[i][j - 1] == "#"):
                    is_possible = False
    if is_possible:
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()

Measured memory_bytes: 3064