akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#define rep(i, a, n) for(int i = a; i < n; i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main()
{
    string s;
    cin >> s;
    string t;
    t = s;
    int ans_1 = 0, ans_2 = 0;
    if(s[0] == '0'){
        rep(i, 1, s.size()){
            if(s[i] == s[i-1]){
                ans_1++;
                if(s[i] == '0'){
                    s[i] = '1';
                }
                else{
                    s[i] = '0';
                }
            }
        }
    }
    else if(s[0] == '1'){
        ans_1++;
        s[0] = '0';
        rep(i, 1, s.size()){
            if(s[i] == s[i-1]){
                ans_1++;
                if(s[i] == '0'){
                    s[i] = '1';
                }
                else{
                    s[i] = '0';
                }
            }
        }
    }
    if(t[0] == '1'){
        rep(i, 1, t.size()){
            if(t[i] == t[i-1]){
                ans_2++;
                if(t[i] == '0'){
                    t[i] = '1';
                }
                else{
                    t[i] = '0';
                }
            }
        }
    }
    else if(t[0] == '0'){
        ans_2++;
        t[0] = '1';
        rep(i, 1, t.size()){
            if(t[i] == t[i-1]){
                ans_2++;
                if(t[i] == '0'){
                    t[i] = '1';
                }
                else{
                    t[i] = '0';
                }
            }
        }
    }
    //cout << ans_1 << ans_2 << endl;
    cout << min(ans_1, ans_2) << endl;
    return 0;
}


Measured memory_bytes: 512
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int h = sc.nextInt();
		int w = sc.nextInt();
		PriorityQueue<Long> qH = new PriorityQueue<>();
		PriorityQueue<Long> qW = new PriorityQueue<>();
		for (int i = 0; i < h; i++) {
		    qH.add(sc.nextLong());
		}
		for (int i = 0; i < h; i++) {
		    qW.add(sc.nextLong());
		}
		long total = 0;
		while (qH.size() > 0 && qW.size() > 0) {
		    if (qH.peek() > qW.peek()) {
		        total += qH.size() * qW.poll();
		    } else {
		        total += qW.size() * qH.poll();
		    }
		}
        System.out.println(total);
	}
}



Measured memory_bytes: 108348
#[allow(unused_imports)]
use std::cmp;
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;
#[allow(unused_imports)]
use proconio::derive_readable;
use proconio::fastout;
#[allow(unused_imports)]
use num::Integer;
#[allow(unused_imports)]
use itertools::Itertools;

#[fastout]
fn main() {
  input! {
    n: usize,
    a: [i64; n],
  }
  let mut sum = vec![0; n+2];
  for (i, &x) in a.iter().enumerate() {
    sum[i+2] = sum[i] + x;
  }
  if n % 2 == 0 {
    let mut ans = - (1i64 << 60);
    let mut i = 0;
    while i <= n {
      ans = cmp::max(ans, sum[i] + sum[n+1] - sum[i+1]);
      i += 2;
    }
    println!("{}", ans);
  } else {
    let mut ans = - (1i64 << 60);
    let mut right = vec![- (1i64 << 60); n+3];
    let mut i = n;
    loop {
      right[i] = cmp::max(right[i+2], sum[i] + sum[n+1] - sum[i+1]);
      if i < 2 {
        break;
      }
      i -= 2;
    }
    let mut j = 0;
    while j < n {
      ans = cmp::max(ans, right[j+1] - sum[j+1] + sum[j]);
      j += 2;
    }
    println!("{}", ans);
  }
}


Measured memory_bytes: 8784
//Keep pluggin',this is your only outlet.
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cctype>
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,b,a) for(int i=b;i>=a;i--)
#define fi first
#define mp make_pair
#define se second
using namespace std;
//#define int long long

inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int quickmul(int x,int y,int mod){return (x*y-(int)((long double)x/mod*y)*mod+mod)%mod;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x * f;
}
const int MAXN = 1e5 + 100;
int n;
pair<int,int>a[MAXN],b[MAXN];
///------------------head------------------
signed main(signed argc, char *argv[]){
    n = read();
    int ans;
    rep(i,1,n) {
        int x = read();
        if (i & 1) ++a[x].fi,a[x].se = x;
        else ++b[x].fi,b[x].se = x;
    }
    sort(a,a+MAXN,greater<pair<int,int> >());
    sort(b,b+MAXN,greater<pair<int,int> >());
    if (a[0].se != b[0].se) ans = n - a[0].fi - b[0].fi;
    else ans = n - max(a[0].fi+b[1].fi,a[1].fi+b[0].fi);
    cout << ans << endl;
    return 0;
}

/* Examples: */
/*

*/

/*

*/


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

template<typename T, typename E> struct LazySegmentTree {
  using F = function<T(T, T)>;
  using G = function<T(T, E)>;
  using H = function<E(E, E)>;
  using P = function<E(E, int)>;

  int n;
  T ti;
  E ei;
  F f;
  G g;
  H h;
  P p;
  vector<T> data;
  vector<E> lazy;

  LazySegmentTree(int n_, F f, G g, H h, T ti = INT_MAX, E ei = INT_MAX,
                  P p = [](E a, int b) { return a; })
      : f(f), g(g), h(h), ti(ti), ei(ei), p(p) {
    init(n_);
  }
  void init(int n_) {
    n = 1;
    while (n < n_) n *= 2;
    data.assign(n * 2 - 1, ti);
    lazy.assign(n * 2 - 1, ei);
  }
  void build(vector<T> v) {
    for (int i = 0; i < v.size(); ++i) data[i + n - 1] = v[i];
    for (int i = n - 2; i >= 0; --i) {
      data[i] = f(data[i * 2 + 1], data[i * 2 + 2]);
    }
  }
  inline void eval(int len, int k) {
    if (lazy[k] == ei) return;
    if (k * 2 + 1 < n * 2 - 1) {
      lazy[k * 2 + 1] = h(lazy[k * 2 + 1], lazy[k]);
      lazy[k * 2 + 2] = h(lazy[k * 2 + 2], lazy[k]);
    }
    data[k] = g(data[k], p(lazy[k], len));
    lazy[k] = ei;
  }
  T update(int a, int b, E x, int k = 0, int l = 0, int r = -1) {
    if (r < 0) r = n;
    eval(r - l, k);
    if (b <= l || r <= a) return data[k];
    if (a <= l && r <= b) {
      lazy[k] = h(lazy[k], x);
      return g(data[k], p(lazy[k], r - l));
    }
    T vl = update(a, b, x, k * 2 + 1, l, (l + r) / 2);
    T vr = update(a, b, x, k * 2 + 2, (l + r) / 2, r);
    return data[k] = f(vl, vr);
  }
  T query(int a, int b, int k = 0, int l = 0, int r = -1) {
    if (r < 0) r = n;
    eval(r - l, k);
    if (b <= l || r <= a) return ti;
    if (a <= l && r <= b) return data[k];
    T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
    T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
    return f(vl, vr);
  }
};

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

  int n, q; cin >> n >> q;
  const int INF = INT_MAX;
  LazySegmentTree<int, int>::F f = [&](int a, int b) { return min(a, b); };
  LazySegmentTree<int, int>::G g = [&](int a, int b) { return (b == INF) ? a : b; };
  LazySegmentTree<int, int>::H h = [&](int a, int b) { return (b == INF) ? a : b; };
  LazySegmentTree<int, int>::P p = [&](int a, int b) { return (a == INF) ? a : a * b; };

  LazySegmentTree<int, int> seg(n, f, g, h);
  for (int i = 0; i < q; ++i) {
    int com; cin >> com;
    if (com) {
      int i; cin >> i;
      cout << seg.query(i, i + 1) << endl;
    } else {
      int s, t, x; cin >> s >> t >> x;
      seg.update(s, t + 1, x);
    }
  }
  return 0;
}



Measured memory_bytes: 4956
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define pb push_back
#define all(x) x.begin(), x.end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define reps(i, m, n) for (int i = m; i <= n; ++i)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;

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

  int n, d; cin >> n >> d;

  int x[100][100];
  rep(i, n) {
    rep(j, d) {
      cin >> x[i][j];
    }
  }

  int ans = 0;

  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {

      int norm = 0;

      for (int k = 0; k < d; ++k) {
        int diff = abs(x[i][k] - x[j][k]);
        norm += diff * diff;
      }

      bool flg = false;

      for (int k = 0; k <= norm; ++k) {
        if( k * k == norm ) flg = true;
      }

      if( flg ) ++ans;
    }
  }

  cout << ans << endl;

  return 0;
}

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

int main(){
	char A[15], B[15], C[15];
	scanf("%s %s %s", &A, &B, &C);
	
	int lastCharA = strlen(A) - 1;
	int lastCharB = strlen(B) - 1;
	
	if(A[lastCharA] == B[0] && B[lastCharB] == C[0]){
		puts("YES");
	}
	else{
		puts("NO");
	}
	
	return 0;
}

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

int main(){
  int input;
  int sum = 0;
  cin >> input;
  
  for(int i=0; i<3; i++){
    if(input % 10 == 1){
      sum++;
    }
    input /= 10;
  }
  
  cout << sum << endl;
  return 0;
}

Measured memory_bytes: 256
// https://atcoder.jp/contests/abc085/tasks/abc085_b

#include <bits/stdc++.h>
#define REP(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define REPR(i, n) for (int(i) = (n); (i) >= 0; (i)--)
#define FOR(i, m, n) for (int(i) = (m); (i) < (n); i++)
#define INF 1e9
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;

int main()
{
  /* Magic word */
  // cin.tie(0);
  // ios::sync_with_stdio(false);
  /* ---------- */

  int n, di;
  set<int> d;

  cin >> n;
  while (n--)
  {
    cin >> di;
    d.insert(di);
  }

  cout << d.size() << endl;

  return 0;
}


Measured memory_bytes: 256
// #include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

#define rep(i,n) for (int i = 0; i < n; ++i)
#define repr(i,n) for (int i = n; i > 0; --i)
using namespace std;
using ll = long long;
using P = pair<int,int>;

const int MAX = 100;
const int INF = (1<<12);

int main() {
  string s;
  cin >> s;
  char p,n;
  if (s.size() == 1) {
    if(s[0] == '?') s[0] = 'D';
    cout << s << endl;
    return 0;
  }
  rep(i,s.size()-1){
    p = s[i];
    n = s[i+1];
    if(p == '?'){
      if(n == '?'){
        s[i] = 'D';
        s[i+1] = 'D';
        i++;
      }else if(n == 'P'){
        s[i] = 'D';
      }else if(n == 'D'){
        s[i] = 'P';
      }
    } else if (p == 'P' || p == 'D'){
      if(n == '?'){
        s[i+1] = 'D';
      }
    }
  }
  cout << s << endl;
  return 0;
}

Measured memory_bytes: 3716
import math
import sys

def getinputdata():

    # 配列初期化
    array_result = []
    
    data = input()

    
    array_result.append(data.split(" "))

    flg = 1

    try:


        while flg:

            data = input()

            array_temp = []

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = 1

            else:

                flg = 0
    finally:


        return array_result





arr_data = getinputdata()

s = arr_data[0][0]

print(s[0:4] + " " + s[4:])


Measured memory_bytes: 3060
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;
ll A[100005];
int main() {
  ios::sync_with_stdio(false);
  ll A;
  string Bs;
  cin >> A;
  cin >> Bs;
  ll B = Bs[0] - '0';
  B = B * 10 + Bs[2] - '0';
  B = B * 10 + Bs[3] - '0';
  ll ret = A * B / 100;
  cout << ret << endl;
}

Measured memory_bytes: 3652
x, y = map(int, input().split())
a = [1, 3, 5, 7, 8, 10, 12]
b = [4, 6, 9, 11]
c = [2]
if (x in a and y in a) or (x in b and y in b) or (x in c and y in c):
  print("Yes")
else:
  print("No")

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

#define ll long long

using namespace std;

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    ll arr[n], pre[n];
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
        pre[i] = (i ? pre[i - 1] : 0) + arr[i];
    }

    ll dp[n][n];
    for(int len = 0; len < n; len++) {
        for(int l = 0; l < n - len; l++) {
            int r = l + len;
            if(len == 0) {
                dp[l][r] = 0;
                continue;
            }

            dp[l][r] = LONG_MAX;
            ll sum = pre[r] - (l ? pre[l - 1] : 0);
            for(int k = l; k < r; k++)
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + sum);
        }
    }

    cout << dp[0][n - 1] << endl;
    return 0;
}


Measured memory_bytes: 1536
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstdlib>
#define LL long long
#define LD long double
using namespace std;
const int NN=100 +117;
const int MM=100 +117;
int read(){
	int fl=1,x;char c;
	for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
	if(c=='-'){fl=-1;c=getchar();}
	for(x=0;c>='0'&&c<='9';c=getchar())
		x=(x<<3)+(x<<1)+c-'0';
	return x*fl;
}
void open(){
	freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
}
void close(){
	fclose(stdin);
	fclose(stdout);
}


int m,n;
int fin,st;
int pcnt=0;
struct node{
	int id,xt;
	int to,rem;
}e[NN*NN*2]={};
int ecnt=1;

int p[2*NN]={};
void add(int a,int b,int rem,int id){
	e[++ecnt].to=b;
	e[ecnt].rem=rem;
	e[ecnt].id=id;
	e[ecnt].xt=p[a];
	p[a]=ecnt;
}
void link(int a,int b,int rem,int id){
	add(a,b,rem,id);
	add(b,a,0,id);
}
int a[NN][NN]={};
int b[NN][NN]={};
int c[NN][NN]={};
int ord[NN]={};
int g[2*NN]={};
int h[2*NN]={};
int q[2*NN]={};
bool used[NN*NN]={};
bool bfs(){
	int std=h[fin]+3;
	h[st]=std;
	int hd=0,tl=0;
	q[tl++]=st;
	while(hd!=tl){
		int x=q[hd++];
		if(x==fin)break;
		for(int pos=p[x];pos;pos=e[pos].xt){
			if(!e[pos].rem)continue;
			int cur=e[pos].to;
			if(h[cur]<std){
				h[cur]=h[x]+1;
				q[tl++]=cur;
			}
		}
	}
	return h[fin]>std;
}
int dfs(int x,int f){
	if(x==fin)return f;
	int res=0;
	for(int &pos=g[x];pos;pos=e[pos].xt){
		int cur=e[pos].to;
		if(!e[pos].rem||h[cur]!=h[x]+1)continue;
		int tp=dfs(cur,min(e[pos].rem,f));
		if(tp){
			f-=tp,res+=tp;
			e[pos].rem-=tp;
			e[pos^1].rem+=tp;
		}
		if(!f){
			break;
		}
	}
	return res;
}
int getf(){
	int f=0;
	while(bfs()){
		for(int i=1;i<=pcnt;++i){
			g[i]=p[i];
		}
		f+=dfs(st,1e9);
	}
	//cerr<<f<<endl;
	return f;
}
int main(){
	//open();
	n=read();
	m=read();
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			a[i][j]=read();
		}
	}
	pcnt=2*n+2;
	st=pcnt-1;
	fin=pcnt;
	for(int i=1;i<=n;++i){
		link(st,i,1,0);
		link(i+n,fin,1,0);
	}
	int sid=ecnt;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			link(i,n+(a[i][j]+m-1)/m,1,a[i][j]);
		}
	}
	for(int i=1;i<=m;++i){
		getf();
		for(int j=1;j<=n;++j){
			for(int pos=p[j];pos;pos=e[pos].xt){
				if(!e[pos].rem&&!used[e[pos].id]){
					used[e[pos].id]=1;
					b[j][i]=e[pos].id;
					ord[j]=e[pos].id;
					e[pos^1].rem=0;
				}
			}
		}
		sort(ord+1,ord+1+n);
		for(int j=1;j<=n;++j)c[j][i]=ord[j];
		for(int i=2;i<=sid;++i){
			e[i].rem^=1;
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			printf("%d ",b[i][j]);
		}
		putchar('\n');
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			printf("%d ",c[i][j]);
		}
		putchar('\n');
	}
	close();
	return 0;
}

Measured memory_bytes: 896
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <queue>
#include <stack>

using namespace std;

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

const ll mod = 1000000007;

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

  int n, m;
  cin >> n >> m;

  int singleTime = 1900 * m + 100 * (n - m);
  int expectedSub = 1 << m;
  int totalTime = singleTime * expectedSub;

  cout << totalTime << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
#define all(x) (x).begin(), (x).end()
#define endl '\n'
const ll inf = LLONG_MAX;
const long double pi = M_PI;
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}

int main() {
  ll x;
  cin >> x;
  if (x < 1200) cout << "ABC" << endl;
  else cout << "ARC" << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(int argc,char *argv[])
{
    int a,b,c,d;
    scanf("%d %d %d %d\n",&a,&b,&c,&d);
    while(1){
        c=c-b;
        if(c<=0){
            printf("Yes\n");
            break;
        }
        a=a-d;
        if(a<=0){
            printf("No\n");
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 1640
#include "bits/stdc++.h"
#define all(x) (x).begin(), (x).end()

using namespace std;

const int MSIZE = 3003;

double dp[MSIZE][MSIZE];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    memset(dp, 0, sizeof dp);
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        double p;
        cin >> p;
        for (int j = 0; j <= i; j++) {
            dp[i][j] = (dp[i - 1][j] * (1 - p) + dp[i - 1][j - 1] * p);
        }
    }

    double answer = 0;
    for (int i = n; i > n - i; i--) {
        answer += dp[n][i];
    }
    cout << fixed << setprecision(15) << answer << endl;    
}


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

int main() {
  long n,m,x,y;
  cin >> n >> m >> x >> y;
  vector<long> xv(n);
  vector<long> yv(m);
  for(long i=0;i<n;i++) cin >> xv[i];
  for(long i=0;i<m;i++) cin >> yv[i];
  sort(xv.begin(),xv.end());
  sort(yv.begin(),yv.end());
  if(max(x,xv[n-1])<min(y,yv[0])) cout << "No ";
  cout << "War" << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string n;int ans1,i,cnt,ans2;
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin>>n;
	for(i=0;i<n.size();++i)ans1+=n[i]-'0';
	for(i=1,ans2=n[0]-'0'-1;i<n.size();++i)ans2+=9;
	cout<<max(ans1,ans2)<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
typedef complex<double> Point;
typedef vector<Point> VP;
#define X real()
#define Y imag()
const double EPS = 1e-9;
#define EQ(n,m) (abs((n)-(m)) < EPS)

double dot(Point a, Point b) {
  return a.X*b.X + a.Y*b.Y;
}

double cross(Point a, Point b) {
  return a.X*b.Y - a.Y*b.X;
}

int ccw(Point a, Point b, Point c) {
  b -= a;  c -= a;
  if (cross(b,c) >  EPS) return +1;  // counter clockwise
  if (cross(b,c) < -EPS) return -1;  // clockwise
  if (dot(b,c)   < -EPS) return +2;  // c--a--b on line
  if (norm(b) < norm(c)) return -2;  // a--b--c on line or a==b
  return 0;                          // a--c--b on line or a==c or b==c
}

bool isecSP(Point a1, Point a2, Point b) {
  return !ccw(a1, a2, b);
}

Point proj(Point a1, Point a2, Point p) {
  return a1 + dot(a2-a1, p-a1)/norm(a2-a1) * (a2-a1);
}

VP crosspointSC(Point a1, Point a2, Point c, double r) {
  VP ps;
  Point ft = proj(a1, a2, c);
  if (r*r < norm(ft-c)) return ps;
  Point dir = sqrt(max(r*r - norm(ft-c), 0.0)) / abs(a2-a1) * (a2-a1);
  if(isecSP(a1,a2,ft+dir)) ps.push_back(ft+dir);
  if (!EQ(r*r, norm(ft-c)) && isecSP(a1,a2,ft-dir))
    ps.push_back(ft-dir);
  return ps;
}

/* ????????????a??¨????????????b??????????§?[-M_PI,+M_PI] */
double angle(Point a,Point b){
    double t = -arg(a);
    return arg(Point(b.X*cos(t)-b.Y*sin(t),b.X*sin(t)+b.Y*cos(t)));    
}

int main(void){
    int n;
    double r,x,y;
    cin>>n>>r;
    VP ps(n);
    rep(i,n){
        cin>>x>>y;
        ps[i] = Point(x,y);
    }

    double area=0;
    rep(i,n){
        Point p=ps[i], q=ps[(i+1)%n];
        VP cp = crosspointSC(p,q,Point(0,0),r);
        if(abs(p)<r && abs(q)<r){
            assert(cp.size()==0);
            area += cross(p,q)/2.0;
        }
        else if(abs(p)<r && abs(q)>=r){
            assert(cp.size()==1);
            area += cross(p,cp[0])/2.0;
            area += r*r*angle(cp[0],q)/2.0;
        }
        else if(abs(p)>=r && abs(q)<r){
            assert(cp.size()==1);
            area += r*r*angle(p,cp[0])/2.0;
            area += cross(cp[0],q)/2.0;
        }
        // abs(p)>=r && abs(q)>=r
        else if(cp.size()==2){
            if(abs(p-cp[0])>abs(p-cp[1])) swap(cp[0],cp[1]);
            area += r*r*angle(p,cp[0])/2.0;
            area += cross(cp[0],cp[1])/2.0;
            area += r*r*angle(cp[1],q)/2.0;
        }
        else area += r*r*angle(p,q)/2.0;
    }
    printf("%.10f\n",area );

    return 0;
}

Measured memory_bytes: 3740
#include <cstdio>
#include <utility>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#define REP(i,n) for(int i=0;i<n;i++)
typedef long long ll;
using namespace std;
typedef vector<ll> vl;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;
typedef vector<string> vs;

int main() 
{
	int n;
	cin >> n;
	cin.ignore();
	REP(i,n){
		
		string s,c;
		getline(cin,s);
		getline(cin,c);
		
		char a[10]={'0','1','2','3','4','5','6','7','8','9'};
		
		REP(j,s.length()){
			switch(s[s.length()-1-j]){
				case 'C':
				rotate(c.begin(),c.begin()+1,c.begin()+c.length());
				break;
				case 'J':
				rotate(c.begin(),c.begin()+c.length()-1,c.begin()+c.length());
				break;
			  case 'E':{
				string tmp1="";string tmp2="";string tmp3="";
				REP(k,c.length()/2){tmp1+=c[k];}
				REP(k,c.length()/2){tmp3+=c[c.length()-c.length()/2+k];}
				if(c.length()%2==1){tmp2+=c[c.length()/2];}
				c = tmp3+tmp2+tmp1;}
				break;
				case 'A':
				reverse(c.begin(),c.end());
				break;
				case 'M':
				REP(k,c.length()){REP(l,10){if(a[l]==c[k]){c[k]=a[(l+1+10)%10];break;}}}
				break;
				case 'P':
				REP(k,c.length()){REP(l,10){if(a[l]==c[k]){c[k]=a[(l-1+10)%10];break;}}}
				break;
			}
		}
		cout << c << endl;
	}	
		return 0;
}

Measured memory_bytes: 1228
#x=今まで使った文字種数、→次はaとα個のもの。つまり1つふえる
import sys
sys.setrecursionlimit(4100000)
n=int(input())
def dfs(s, mx):
    if len(s)==n:
        print(s)
        return 0
    for i in range(ord('a'), mx+2):# ord('a')からmx+1までの数字を使いたい
        t=str(s)
        moji=str(chr(i))
        t+=moji
        dfs(t, max(mx, i))
dfs('',ord('a')-1)

Measured memory_bytes: 4412
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>

using namespace std;

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

int main(){
	int n;
	int ans;
	
	while(1){
		cin >> n;
		if(!n) break;
		ans = 0;
		for(int i=0;i*i<=n;i++){
			for(int j=i;i*i+j*j<=n;j++){
				for(int k=j;i*i+j*j+k*k<=n;k++){
					for(int m=k;i*i+j*j+k*k+m*m<=n;m++){
						if(i*i+j*j+k*k+m*m==n) ans++;
					}
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 1164
#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb push_back
#define endl '\n'
#define MOD 1000000007
#define MOD2 998244353

using namespace std;
typedef long long int ll;

int par[100010], dist[100010];
int ct[100010];
vector<vector<int>> rev(100010);

void dfs(vector<vector<int>> &g, int u)
{
	for (auto x : g[u])
	{
		--ct[x];
		if (dist[x] < 1 + dist[u])
		{
			dist[x] = 1 + dist[u];
			par[x] = u;
		}
		if (!ct[x]) dfs(g, x);
	}
}

int main(void)
{
	fast;
	#ifdef LOCAL
	freopen("in", "r", stdin);
	freopen("out", "w", stdout);
	#endif
	
	int n, m; cin >> n >> m;
	vector<vector<int>> g(n);
	bool no[n] = {0};
	int root = 0;
	for (int i = 0; i < n-1+m; ++i)
	{
		int u, v; cin >> u >> v;
		g[--u].pb(--v);
		rev[v].pb(u);
		no[v] = 1;
		++ct[v];
		while (no[root]) ++root;
	}
	par[root] = -1;
	dfs(g, root);
	for (int i = 0; i < n; ++i)
	{
		cout << par[i]+1 << endl;
	}
}

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

int BOARD_N[100][100];
int BOARD_M[100][100];

bool isPattern(int h, int w, int M) {
  for(int y = 0; y < M; ++y) {
    for(int x = 0; x < M; ++x) {
      if(BOARD_N[h + y][w + x] != BOARD_M[y][x]) {
        // cout << h << ", " << w << " : " << BOARD_N[h + y][w + x] << " => " << y << ", " << x
        //    << " : " << BOARD_M[y][x] << endl;

        return false;
      }
    }
  }
  return true;
}

int main() {
  int N, M;
  cin >> N >> M;
  {
    string s;
    for(int n = 0; n < N; ++n) {
      cin >> s;
      for(int i = 0; i < N; ++i) {
        BOARD_N[n][i] = (s[i] == '#') ? 1 : 0;
      }
    }
  }
  {
    string s;
    for(int m = 0; m < M; ++m) {
      cin >> s;
      for(int i = 0; i < M; ++i) {
        BOARD_M[m][i] = (s[i] == '#') ? 1 : 0;
      }
    }
  }
  for(int h = 0; h <= N - M; ++h) {
    for(int w = 0; w <= N - M; ++w) {
      if(isPattern(h, w, M)) {
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
	int a[5];
	int b;
	int i, j;
	int max;
	
	while (1) {
		for (i = 0; i < 5; i++) {
			if (scanf("%d", &a[i]) == EOF) {
				return 0;
			}
		}
		
		for (i = 0; i < 5; i++) {
			max = i;
			for (j = i + 1; j < 5; j++) {
				if (a[max] < a[j]) {
					max = j;
				}
			}
			b = a[max];
			a[max] = a[i];
			a[i] = b;
		}
		
		for (i = 0; i < 5; i++) {
			printf("%d", a[i]);
			if (i < 4) {
				printf(" ");
			}
			else {
				printf("\n");
			}
		}
	}
}

Measured memory_bytes: 600
import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static int N = sc.nextInt();
    static int M = sc.nextInt();
    static int X = sc.nextInt();
    static int price[] = new int[N];
    static int al[][] = new int[N][M];



    public static void main(String[] args) {
        //標準入力を取得
        for (int i = 0; i < N; i++){
            price[i] = sc.nextInt();
            for (int j = 0; j < M; j++){
                al[i][j] = sc.nextInt();
            }
        }
        int result = 10000000;
        //bit全探索
        for (int bit = 0; bit < (1<<N); bit++){
            int cost = 0;
            int level[] = new int[M];
            for (int i = 0; i < N; i++){
                //bitが1だったら
                if ((bit>>i&1) == 1){
                    //本の値段を足して
                    cost += price[i];
                    for (int j = 0; j < M; j++){
                        //アルゴリズムレベルを上げる
                        level[j] += al[i][j];
                    }
                }
            }
            boolean check = true;
            //確認
            for (int i = 0; i < M; i++){
                if (level[i] < X) check = false;
            }
            if (check){
                result = Math.min(result, cost);
            }
        }

        if (result != 10000000){
            System.out.println(result);
        } else {
            System.out.println(-1);
        }
    }

}


Measured memory_bytes: 37420
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 1000000007

int main() {
	ll n,k,ans=1<<30;
	vector<ll>a;
	cin>>n>>k;
	for(int i=0;i<n;i++){
		int z;
		cin>>z;
		a.push_back(z);
	}
	sort(a.begin(),a.end());
	for(int i=k-1;i<n;i++){
		ans=min(ans,a[i]-a[i-(k-1)]);
	}
	cout <<ans;
	return 0;
}

Measured memory_bytes: 1400
#include<bits/stdc++.h>
using namespace std;
#define ll  long long
#define endl '\n'
#define FASTINOUT ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const ll mod = 1000000007;
const double PI = 3.141592653589793238463;
const int N=5e5+10;
int main()
{
    FASTINOUT;
    int x,y;
    cin>>x>>y;
    cout<<x+(y>=x?0:-1)<<endl;
    return 0;
}


Measured memory_bytes: 256
//include
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath> 
#include <iomanip>
#include <math.h>
#include <utility>
#include <functional>
#include <cstdlib>//絶対値　abs()
//using
using namespace std;
using vl = vector <long long>;
using vs = vector <string>;
using vc = vector <char>;
using ll= long long;
using vvl = vector<vector<ll> >;
//vector<vector<char> > hyou(N, vector<char>(N));
using vd = vector <double>;
//define
//#define int long long
#define rep(i,n) for(int i=0; i<n; i++)
#define print(n) cout<<n<<endl;
#define sortp(d) sort(d.begin(),d.end()) //1234
#define sortm(d) sort(d.rbegin(),d.rend()) //4321
//素数判定　O(√A) 
bool is_prime(int x){
 if(x<=1) return false;
 for(int i=2;i*i<=x;i++)
 if(x%i==0) return false;
 return true;
 }
/*順列生成
do {
  // 順列に対する処理
} while (next_permutation(配列変数.begin(), 配列変数.end()));*/

//グローバル変数宣言
 ll p=0,q=0,r=0;

int main(){
  ll x;
  cin>>x;
  if (x==0)
  {
    print(1);
  }else print(0);
  
}

Measured memory_bytes: 3632
import numpy as np
 
N,T = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB = sorted(AB)

can_add = [0]*N
for n in range(N-1, 0, -1):
  x = can_add[n]
  y = AB[n][1]
  can_add[n-1] = x if x>y else y

dp = np.zeros(T,np.int64)  
ans = 0
for i, (a,b) in enumerate(AB):
  np.maximum(dp[a:], dp[:-a].copy()+b, out=dp[a:])
  x = dp.max() + can_add[i]
  if ans < x:
    ans = x
print(ans)     

Measured memory_bytes: 18492
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define repi(i,x,n) for(ll i=x;i<(ll)(n);i++)
#define lb lower_bound
#define ub upper_bound
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
const ll mod = 1000000007;
const ll INF = 1000000099;
vector<ll> dx={-1,1,0,0},dy={0,0,-1,1};
//cin.tie(0);ios::sync_with_stdio(false);



signed main(){
    ll n,q;cin>>n>>q;

    multimap<ll,ll> ma;

    rep(i,n){
        ll s,t,x;cin>>s>>t>>x;
        
        ma.emplace(max(0ll,s-x),x);

        ma.emplace(max(0ll,t-x),-x);
    }


    auto i=ma.begin();
    multiset<ll> se;
    rep(z,q){
        ll d;cin>>d;
        
        while((*i).fi<=d && i!=ma.end()){
            ll x=(*i).se;
            if(x>0){
                se.emplace(x);
            }else{
                auto itr=se.lower_bound(-x);
                if(itr!=se.end()){
                    //cout<<"dasi"<<siz(se)<<" "<<*itr<<endl;
                    se.erase(itr);
                    //cout<<"dasita"<<siz(se)<<endl;
                }
            }
            i++;
        }


        if(siz(se)==0){
            cout<<-1<<endl;
        }else{
            cout<<*(se.begin())<<endl;
        }

    }
}

Measured memory_bytes: 35584
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
#define yn {puts("Yes");}else{puts("No");}
#define MAX_N 25

int main() {
    int n, k;
    ll l, r;
    cin >> n >> k >> l >> r;
    ll a[n];
    rep(i,n)cin >> a[i];
    sort(a,a+n);
    vector<ll> v[k+1];
    rep(i,1<<(n/2)){
        int cnt = __builtin_popcount(i);
        if(cnt > k) continue;
        bitset<MAX_N> f(i);
        ll tmp = 0;
        rep(j,n/2){
            if(f[j]) tmp += a[j];
        }
        v[cnt].push_back(tmp);
    }
    
    rep(i,k+1)sort(v[i].begin(), v[i].end());

    int m = n - n/2;
    rep(i,m) a[i] = a[i+n/2];

    ll ans = 0;

    rep(i,1<<m){
        int cnt = __builtin_popcount(i);
        if(cnt > k) continue;
        bitset<MAX_N> f(i);
        ll tmp = 0;
        rep(j,m){
            if(f[j]) tmp += a[j];
        }
        ans += upper_bound(v[k-cnt].begin(), v[k-cnt].end(), r-tmp) - lower_bound(v[k-cnt].begin(), v[k-cnt].end(), l-tmp);
    }

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



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

int main()
{
    int n,l;
    cin >> n>>l;
    int tmp=0;
    for(int i=l;i<=n+l-1;i++){
        tmp+=i;
    }
    int k=n+l-1;
    if(l*k>0){
        if(l>0)tmp-=l;
        else tmp-=k;
    }
    cout << tmp << endl;
    return 0;
}


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

int main(void){
    int a,b;
    cin >> a >> b;
    ll dis = b-a;
    ll num = 0;
    for(int i=1;i<=dis;i++){
        num += i;
    }
    ll ans = num - b;
    
    cout << ans <<endl;
    
    
    return 0;
}
























































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

int main(){
    int h,w;
    scanf("%d %d",&h,&w);
    char c[w+10];
    for (int i=0;i<h;i++) {
        scanf("%s",c);
        printf("%s\n",c);
        printf("%s\n",c);
    }
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
  int main() {
  int N, A; 
  cin >> N >> A;
  int L = A;
  int R = A + N - 1;
  int eat;
  if (R <= 0) {eat=R;}
  else if (L >= 0) {eat=L;}
  else eat=0;
  int answer = (R + L) * (R - L + 1) / 2 - eat;
  cout << answer << endl;
  return 0;
}

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

int main() {
    int N, Y;
    cin >> N >> Y;
    int res10000 = -1, res5000 = -1, res1000 = -1;
    for (int a = 0; a <= N; ++a) {  // 10000円の枚数を 0 〜 N で調べる
        for (int b = 0; b + a <= N; ++b) {  // 5000円の枚数を 0 〜 N-a で調べる
            int c = N - a - b;  // 1000円の枚数は決まる
            int total = 10000*a + 5000*b + 1000*c;
            if (total == Y) {  // 答えが見つかったら
                res10000 = a;
                res5000 = b;
                res1000 = c;
            }
        }
    }

    // 答えを出力 (見つかっていなくても -1 -1 -1 になるので OK です)
    cout << res10000 << " " << res5000 << " " << res1000 << endl;
}

Measured memory_bytes: 3548
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <numeric>
using namespace std;

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

	vector<int> score;
	
	for (int i = 0; i < n; i++)
	{
		int p;
		cin >> p;
		score.push_back(p);
	}
		
	long long sum = accumulate(score.begin(), score.end(), 0);

	if (sum > m) {
		cout << -1 << endl;
	}
	else {
		cout << m - sum << endl;
	}

	return 0;
}

Measured memory_bytes: 3704
#include<stdio.h>
int main(void){
    int H, W, i, j;
    while(1){
        scanf("%d %d", &H, &W);
        if(H == 0 && W == 0){return 0;}
        for(i = 0; i < H; i++){
            for(j = 0; j < W; j++){
                printf("#");
            }
            printf("\n");
        }
        printf("\n");
    }
    return 0;
}


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

int main()
{
  int A, B, C, X;
  int count = 0;

  cin >> A >> B >> C >> X;
  for (int i = 0; i <= A; i++)
  {
    if (X < (i * 500))
      break;
    else if (X == (i * 500))
    {
      count++;
      break;
    }
    for (int j = 0; j <= B; j++)
    {
      if (X < (i * 500 + j * 100))
        break;
      else if (X == (i * 500 + j * 100))
      {
        count++;
        break;
      }
      for (int k = 0; k <= C; k++)
      {
        if (X < (i * 500 + j * 100 + k * 50))
          break;
        else if (X == (i * 500 + j * 100 + k * 50))
        {
          count++;
          break;
        }
      }
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#include <queue>


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

using namespace std;
using ll=long long;

int main(){
  int n;
  cin >> n;
  int a = n%10;
  int b = (n/10)%10;
  int c = (n/100)%10;
  cout << (10-c)*100 + (10-b)*10 + (10-a) << endl;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
mod = 10 ** 9 + 7
table = [0] * (K + 1)
table[1] = K
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors
for i in range(2, K + 1): table[i] = (K // i) % mod
res = 0
tt = [0] * (K + 1)
for i in range(K, 0, -1):
  t = pow(table[i], N, mod) + tt[i]
  divs = make_divisors(i)
  #print(divs, t)
  for d in divs:
    if d < i: tt[d] -= t
  res += t * i % mod
  res %= mod
  #print(res)
print(res)

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

int main() {

    // input from txt （提出時にこの箇所は削除すること）
    //std::ifstream in("input.txt");
    //std::cin.rdbuf(in.rdbuf());
    
    string S;
    cin >> S;
    if(S[S.size()-1] == '3'){
        cout << "bon" << endl;
    }
    else if(S[S.size()-1] == '0' || S[S.size()-1] == '1' || S[S.size()-1] == '6' || S[S.size()-1] == '8'){
        cout << "pon" << endl;
    }
    else{
        cout << "hon" << endl;
    }
    
}



Measured memory_bytes: 3628
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const ll mod = 1000000007;
const int INF = 1001001001;

int main(){
  int n;
  cin >> n;
  if(n==1){
    cout << 1 << endl;
    return 0;
  }
  int minimum;
  cin >> minimum;
  int count = 1;
  rep(i,n-1){
    int a; cin >> a;
    if(a<minimum) count++;
    minimum = min(minimum,a);    
  }
  cout << count << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=10000;
int n,m,x,y,fir[N],nxt[N],to[N],cnt,a[N/10][N/10],sum,vis[N/10],ca[N],is[N];
inline void add(int u,int v)
{
	to[++cnt]=v;nxt[cnt]=fir[u];fir[u]=cnt;
}
void df5(int deep)
{//cout<<deep<<endl;
	if(is[deep])return;
	is[deep]=1;
	for(int i=fir[deep];i;i=nxt[i])
	{
		df5(to[i]);
		for(int j=1;j<=n;j++)
		{
			if(a[to[i]][j])a[deep][j]=1;
		}a[deep][to[i]]=1;
	}
}
int dfs(int deep)
{
	if(vis[deep])return 0;
	vis[deep]=1;
	for(int i=fir[deep];i;i=nxt[i])
	{
		if(!vis[ca[to[i]]])
		{
			if(!ca[to[i]]||dfs(ca[to[i]]))
			{
				ca[to[i]]=deep;
				return 1;
			}
		}
	}return 0;
}
int main()
{
	cin>>n>>m;
	if((n*m)%2)cout<<"Yes";else cout<<"No";return 0;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		add(x,y);
	}
	for(int i=1;i<=n;i++)
	df5(i);
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		if(is[i])
		{
			memset(vis,0,sizeof(vis));
			ans+=dfs(i);
		}
	}
	printf("%d\n",n-ans);
	for(int i=1;i<=n;i++)
	printf("%d",ca[i]?1:0);
	printf("\n");
	
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define ll long long

ll N, H;
vector<ll> a,b;

ll max_vec(vector<ll> v){
	ll ans = 0;
	for(auto e:v){
		ans = max(ans,e);
	}
	return ans;
}


int solve(){
	ll count = 0;
	ll max = max_vec(a);

	sort(b.begin(), b.end());
	reverse(b.begin(),b.end());

	for(auto e:b){
		if(max < e){
			H -= e;
			count++;
			if(H <= 0){
				cout << count << endl;
				return 0;
			}
		} 
	}

	if(H%max == 0) count += H/max;
	else count += H / max + 1;

	cout << count << endl;

	return 0;
}

int main(){
	cin >> N >> H;
	a.resize(N); b.resize(N);
	for(int i=0;i<N;i++){
		cin >> a[i] >> b[i];
	}
	solve();
	return 0;
}

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

using ll = long long;

const int MAX_N = 1e5+10;
const long long INF = 0x3f3f3f3f3f3f3f3f;
int N, a[MAX_N];
ll dp[MAX_N][2];

void solve()
{
    //dp[i][j]: max value a[0]..a[i-1], j sign before a[i] is changed?
	dp[1][0]=a[0];
	dp[1][1]=-a[0];
	for(int i=1;i<N;++i){
		dp[i+1][0] = max(dp[i][0]+a[i], dp[i][1]-a[i]);
		dp[i+1][1] = max(dp[i][0]-a[i], dp[i][1]+a[i]);
	}
	cout << dp[N][0] << endl;
}

int main()
{
	ios::sync_with_stdio(false);
	cin >> N;
	for(int i=0;i<N;++i)cin>>a[i];
	solve();
	return 0;
}

Measured memory_bytes: 2176
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
constexpr ll INF = (1LL << 30) - 1LL;
constexpr ll LINF = (1LL << 60) - 1LL;
constexpr ll MOD = 1e9 + 7;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    if (n % 2) {
        cout << 0 << endl;
    } else {
        ll s = 2, res = 0;
        for (ll i = 0; i < 25; i++) {
            s *= 5LL;
            res += n / s;
        }
        cout << res << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <cstdlib>


using namespace std;

struct Node {
  int key;
  Node *prev, *next;
};

Node *nil;

void init() {
  nil = (Node *)malloc(sizeof(Node));
  nil->next = nil;
  nil->prev = nil;
}

void printList() {
  Node *cur = nil->next;
  int count = 0;
  while(true) {
    if(cur == nil) break;
    if(count++ > 0) cout << " ";
    printf("%d", cur->key);
    cur = cur->next;
  }
  cout << endl;
}

void insert(int key){
  Node *x = (Node *)malloc(sizeof(Node));
  x->key = key;
  // 番兵の直後に要素を追加
  x->next = nil->next;
  nil->next->prev = x;
  nil->next = x;
  x->prev = nil;
}

Node* listSearch(int key) {
  Node *cur = nil->next; //番兵の次の要素から巡る
  while (cur != nil && cur->key != key) {
    cur = cur->next;
  }
  return cur;
}

void deleteNode(Node *t) {
  if( t == nil) return; //tが番兵の場合は処理しない
  t->prev->next = t->next;
  t->next->prev = t->prev;
  free(t);
}

void deleteFirst() {
  deleteNode(nil->next);
}

void deleteLast() {
  deleteNode(nil->prev);
}

void deleteKey(int key){
  deleteNode(listSearch(key));
}

int main()
{
  int key, n;
  scanf("%d", &n);
  char command[30];
  init();
  for (int i = 0; i < n; i++){
    scanf("%s%d", command, &key);
    if(command[0] == 'i') insert(key);
    else if (command[0] == 'd') {
      if(strlen(command) > 6) {
        if(command[6] == 'F') deleteFirst();
        else if(command[6] == 'L') deleteLast();
      } else {
        deleteKey(key);
      }
    }
  }
  printList();
  return 0;
}


Measured memory_bytes: 34548
#include <bits/stdc++.h>
using namespace std;
struct info
{
  int x,y;
};
vector<info> point;
double hypot(int dx,int dy)
{
  return sqrt(dx*dx + dy*dy);
}
double dist(info a, info b)
{
  return hypot(a.x-b.x,a.y-b.y);
}
double solve(vector<int> vc,int n)
{
   double s=0.0;
   int i,j;
   for(i=1; i<n; i++)
   {
     s+=dist(point[vc[i-1]],point[vc[i]]);
   }
   return s;
}
int main()
{
  int i,j,r,n,cnt=1,x1,y1;
  double sum=0,div;
  vector<int> vec;
 
  cin>>n;
  info p;
  for(i=0; i<n; i++)
  {
   cin>>p.x>>p.y;
   point.push_back(p);
   vec.push_back(i);
  }
  sum+=solve(vec,n);
  while(next_permutation(vec.begin(),vec.end()))
  {
    cnt++;
    sum+=solve(vec,n);
  }
  div=sum/cnt;
  printf("%0.10lf\n", div);
  return 0;

}

Measured memory_bytes: 256
N,M = map(int,input().split())
ans = 0
dis = [[] for _ in range(N)]
info = []
for i in range(M):
    a,b = map(int,input().split())
    info.append([a-1,b-1])
    dis[a-1].append(b-1)
    dis[b-1].append(a-1)

def dfs(p):
    visited[p] = True
    for d in dis[p]:
        if visited[d] is False:
            dfs(d)

def check(start,n):
    global visited
    visited = [False] * N
    a = info[n][0]
    b = info[n][1]
    dis[a].remove(b)
    dis[b].remove(a)
    dfs(start)
    if set(visited) != {True}:
        global ans 
        ans += 1
    dis[a].append(b)
    dis[b].append(a)

for i in range(M):
    check(0,i)

print(ans)

Measured memory_bytes: 3064
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
using System.Numerics;

namespace AtCoder
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }
        static long Mod = (long)1e9 + 7;
        static void Main(string[] args)
        {
            SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            Solve();
            Out.Flush();
            Read();
        }
        static void Solve()
        {
            var N = Sarray()[0];

            var MAX = long.MaxValue / 2;
            var csts = Enumerable.Range(0, (int)N).Select(_ => new long[N]).ToArray();
            var orig = Enumerable.Range(0, (int)N).Select(_ => new long[N]).ToArray();
            for (var i = 0; i < N; ++i)
            {
                var A = Sarray();
                for (var j = 0; j < N; ++j)
                    orig[i][j] = csts[i][j] = A[j];
            }
            for (var k = 0; k < N; ++k) for (var i = 0; i < N; ++i) for (var j = 0; j < N; ++j) csts[i][j] = Min(csts[i][j], csts[i][k] + csts[k][j]);
            var IsSame = true;
            for (var i = 0; i < N; ++i)
            {
                for (var j = 0; j < N; ++j)
                    if (orig[i][j] != csts[i][j])
                        IsSame = false; ;
            }
            if (!IsSame)
            {
                WriteLine(-1);
                return;
            }

            var used = Enumerable.Range(0, (int)N).Select(_ => new bool[N]).ToArray();
            for (var i = 0; i < N; ++i)
            {
                for (var j = i + 1; j < N; ++j)
                {
                    var f = true;
                    for (var k = 0; k < N; ++k)
                    {
                        if (k == i || k == j) continue;
                        if (csts[i][j] >= csts[i][k] + csts[k][j])
                            f = false;
                    }
                    if (f) used[i][j] = true;
                }
            }
            var ans = 0L;
            for (var i = 0; i < N; ++i)
                for (var j = i + 1; j < N; ++j)
                    if (used[i][j]) ans += csts[i][j];
            WriteLine(ans);
        }
    }
}

Measured memory_bytes: 38308
#include <iostream>
#include <iomanip>
#include<math.h>
#include<list>
#include <algorithm>
#include<set>
#include<vector>
#include<math.h>
#include<map>
#include<string>
#include <numeric>
#include <queue>
#include <sstream>

using namespace std;
using ll = long long;
using vll = vector<long long>;
using sll = set<long long>;

template<typename T>
T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T>
T lcm(T a, T b) { return a / gcd(a, b) * b; }

template<typename T>
map<T, T> primeFactor(T n) {
	map<T, T> res;
	for (T i = 2; i * i <= n; ++i) {
		while (n % i == 0) {
			res[i] ++;
			n /= i;
		}
	}
	if (n != 1) res[n] = 1;
	return res;
}

template<typename T>
bool IsPrimeNumber(T num)
{
	if (num <= 2) return true;
	else if (num % 2 == 0) return false;

	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2)
	{
		if (num % i == 0)
		{
			return false;
		}
	}

	return true;
}

long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}


#define in(x) cin >> x
#define out(x) cout << x
#define outn(x) cout << x << '\n'
#define outs(x) cout << x << ' '
#define rep(i,s,e) for(ll i=s;i<e;i++)
#define repeq(i,s,e) for(ll i=s;i<=e;i++)

int main() {
	ll n,ans;
	in(n);
	vll a(n),b(n);
	for (auto& i : a) {
		in(i);
	}

	sort(a.begin(), a.end());
	b[0] = a[0];

	rep(i, 1, n) {
		b[i] = b[i - 1] + a[i];
	}

	ans = n;
	rep(i, 0, n - 1) {
		if (b[i] * 2 < a[i + 1]) {
			ans = n - i - 1;
		}
	}

	outn(ans);
	return 0;

}	


Measured memory_bytes: 1792
//============================================================================
// Name        : AOJ.cpp
// Author      : Akari Fujii
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cctype>
#include <string>
#include<algorithm>

using namespace std;
typedef long long ll;
int main(){

	int x,a,b,c;
	int t=0;

	cin>>a;
	cin>>b;
	cin>>c;
	cin>>x;


	for(int i=0; i<a+1; ++i){
		for(int j=0; j<b+1; ++j){
			for(int k=0; k<c+1; ++k){
				if(500*i+100*j+50*k==x){
					t++;
				}
			}

		}
	}

	cout<<t<<endl;
	return 0;



}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<list>
#include<queue>
#include<functional>
#include<limits.h>
#include<string.h>
#include<algorithm> 
#define int long long
using namespace std;

int a[1000];
vector<int>V;
vector<bool>B;
signed main() {
	int n, k; cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < n; i++) {
		int sum = 0;
		for (int j = i; j < n; j++) {
			sum += a[j];
			V.push_back(sum);
			B.push_back(true);
		}
	}
	int ans = 0;
	for (int i = 50; i >= 0; i--) {
		int c = 0;
		for (int j = 0; j < V.size(); j++) {
			if (B[j] && (V[j] & (1ll << i))) {
				c++;
			}
		}
		if (c >= k) {
			ans += (1ll << i);
			for (int j = 0; j < V.size(); j++) {
				if (!(B[j] && (V[j] & (1ll << i)))) {
					B[j] = false;
				}
			}
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 6256