akhauriyash/Code-Regression huggingface dataset:
/*
これを入れて実行
g++ code.cpp
./a.out
 */
 
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <math.h>
#include <tuple>
#include <iomanip>
#include <bitset>
#include <functional>
#include <cassert>

#define all(x) (x).begin(),(x).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
using namespace std;
typedef long long ll;
typedef long double ld;
 
int dy4[4] = {-1, 0, +1, 0};
int dx4[4] = {0, +1, 0, -1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
 
const long long INF = 1LL << 60;
const ll MOD = 1e9 + 7;
 
bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}
 
ll gcd(ll a, ll b){
	if (b == 0)return a;
	return gcd(b, a % b);
}
 
ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}

ll conbinationMemo[100][100];

void cmemoInit(){
    rep(i, 100){
        rep(j, 100){
            conbinationMemo[i][j] = -1;
        }
    }
}
 
ll nCr(ll n, ll r){
    if(conbinationMemo[n][r] != -1) return conbinationMemo[n][r];
    if(r == 0 || r == n){
        return 1;
    } else if(r == 1){
        return n;
    }
    return conbinationMemo[n][r] = (nCr(n - 1, r) + nCr(n - 1, r - 1));
}
 
ll nPr(ll n, ll r){
    r = n - r;
    ll ret = 1;
    for (ll i = n; i >= r + 1; i--) ret *= i;
    return ret;
}
//-----------------------ここから-----------
ll k;
bool ok = false;
bool check(vector<ll> now){
    //cout << now[0] << " " << now[1] << " " << now[2] << endl;
    return (now[0] < now[1] && now[1] < now[2]); 
}
void dfs(ll cnt, vector<ll> now){
    if(cnt > k) return;
    if(check(now)) ok = true;
    rep(i, 3){
        vector<ll> next = now;
        next[i] *= 2;
        dfs(cnt + 1, next);
    }
}
int main(void){
    vector<ll> a(3);
    rep(i, 3) cin >> a[i];
    cin >> k;

    dfs(0, a);

    if(ok){
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}



Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
#define sz 200005
#define faster_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long long ll;

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

    int a[n+5],sum=0,sm[n+5];
    for(int i=0;i<n;i++) cin>>a[i];

//    sort(a,a+n);

    for(int i=0;i<n;i++){
        sum+=a[i];
        sm[i] = sum;
    }

    int mn = sum;
    for(int i=0;i<n;i++){
        mn = min(mn,abs(sm[i]-sum+sm[i]));
//        cout<<abs(sm[i]-sm[n-1]+sm[i])<<endl;
    }

    cout<<mn<<endl;

    return 0;
}




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

int main() {
    ll depth = 0;
    ll h;
    cin >> h;
    while (h>0) {
        depth++;
        h/=2;
    }
    ll ans = 1;
    for (ll i=0; i<depth; i++) ans*=2;
    cout << ans-1;
    return 0;
}

Measured memory_bytes: 3632
use std::io::Read;
use std::cmp::{min, max};

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let answer = solve(&buf);

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

fn solve(input: &str) -> String {
    let mut iterator = input.split_whitespace();

    let n: usize = iterator.next().unwrap().parse().unwrap();
    let k: usize = iterator.next().unwrap().parse().unwrap();
    let mut a: Vec<isize> = (0..n).map(|_| iterator.next().unwrap().parse().unwrap()).collect();

    for _ in 0..k {
        let mut b: Vec<isize> = vec![0; n];
        for i in 0..n {
            let l: isize = max(0, i as isize - a[i] as isize);
            let r: isize = min(n as isize - 1, i as isize + a[i] as isize);
            b[l as usize] += 1;
            if r + 1 < n as isize {
                b[r as usize + 1] -= 1;
            }
        }
        for i in 1..n {
            b[i] += b[i - 1];
        }
        let mut all_n = true;
        for i in 0..n {
            a[i] = b[i];
            if a[i] != n as isize {
                all_n = false;
            }
        }
        if all_n {
            break;
        }
    }

    let mut result = String::new();
    for i in 0..n {
        result.push_str(&format!("{} ", a[i]));
    }
    return result.trim().to_string();
}


Measured memory_bytes: 7660
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    r = 0
    for i in range(1,n+1,2):
        t = 0
        for j in range(1,i+1,2):
            if i % j == 0:
                t += 1
        if t == 8:
            r += 1
    return r



print(main())


Measured memory_bytes: 5464
#include <bits/stdc++.h>
#define pb push_back
#define MOD 1000000007
#define pii pair<int,int>
#define LL long long int
using namespace std;















void solve() {
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++)
        cin >> a[i];

    unordered_map<LL, int> mp;
    for (int i = 0; i < n; i++)
    {
        LL val = i + a[i];
        if (mp.find(val) == mp.end())
            mp[val] = 1;

        else
            mp[val]++;
    }
    LL ans = 0;
    for (int i = 0; i < n; i++)
    {
        LL val = i - a[i];
        if (mp.find(val) != mp.end())
            ans += mp[val];
    }
    cout << ans << "\n";









}




int main()
{


    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}




Measured memory_bytes: 12172
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <functional>
#include <string>
#include <cstdlib>
#include <numeric>
#include <cstdbool>
#include <map> 
#include<set>
#include<queue>

typedef long long ll;


#define rep(i,n) for(ll i=0;i<n;i++)
using namespace std;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const long long INF = 1000000000000000;
const ll inf = -1e18;
typedef pair<ll, ll> P;
ll ma = 1000000000 + 7;
ll mx = 1000003;
ll h, w, n,m,k; string s,t;
int dis[101][101]; int graph[52][52]; bool vis[52];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
ll gcd(ll x, ll y) {
	if (x % y == 0) return y;
	return gcd(y, x % y);

}
ll lcm(ll a,ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
void comb(vector<vector <ll> >& v) {
	for (ll i = 0; i < v.size(); i++) {
		v[i][0] = 1;
		v[i][i] = 1;
	}
	for (ll k = 1; k < v.size(); k++) {
		for (int j = 1; j < k; j++) {
			v[k][j] = (v[k - 1][j - 1] + v[k - 1][j])%ma;
		}
	}
}

ll GetDigit(ll num) {
	return log10(num) + 1;
}
int sy, sx;
char maze[1010][1010];
P nums[10];
ll bfs(ll goal) {
	queue<P> que;
	rep(i,h){
		rep(j, w) {
			dis[i][j] = -1;
		}
	}
	que.push(P(sy, sx));
	dis[sy][sx] = 0;

	while (que.size() > 0) {
		P p = que.front();
		que.pop();
		if (p.first == nums[goal].first && p.second == nums[goal].second) break;
		for (int i = 0; i < 4; i++) {
			int ny = p.first + dy[i];
			int nx = p.second + dx[i];
			if (0 <= ny && ny < h && 0 <= nx && nx < w && maze[ny][nx] != 'X' && dis[ny][nx] == -1) {
				que.push(P(ny, nx));
				dis[ny][nx] = dis[p.first][p.second] + 1;
			}
		}
	}
	sy = nums[goal].first;
	sx = nums[goal].second;
	return dis[nums[goal].first][nums[goal].second];
}

int main() {
	cin >> n >> k;
	vector<ll> a(n);
	rep(i, n) {
		cin >> a[i];
	}
	sort(a.begin(), a.end(),greater<ll>());
	if (k > a[0]) {
		cout << "IMPOSSIBLE" << endl;
		return 0;
	}
	rep(i, n) {
		if (k == a[i]) {
			cout << "POSSIBLE" << endl;
			return 0;
		}
	}
	ll gc = gcd(a[0],a[1]);
	for (ll i = 2; i < n; i++) {
		gc = gcd(gc, a[i]);
	}
	if (k % gc == 0) {
		cout << "POSSIBLE" << endl;
		return 0;
	}
	cout << "IMPOSSIBLE" << endl;
	return 0;
}



Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const double PI  = acos(-1.0);
const double eps = 1e-8;
const int inf = 2e9;
const LL INF  = 0x3f3f3f3f3f3f3f3f;
const int N=3e5+10;
const int M=1e6+10;
const int mod=1e9+7;
inline LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }
inline LL lcm(LL a, LL b) { return a * b / gcd(a, b); }
inline LL read(){LL x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}return x*f;}
inline LL qpow(LL x,LL k=mod-2,LL m=mod){LL res=1;while(k){if(k&1) res=res*x%m;x=x*x%m;k>>=1;}return res;}
/*=================================================================================================================*/
int n,maxs=-inf,maxd=-inf,mins=inf,mind=inf;


int main(){
    scanf("%d",&n);
    int ans=-inf;
    for(int i=1,x,y;i<=n;i++){
        scanf("%d%d",&x,&y);
        maxs=max(maxs,x+y);
        mins=min(mins,x+y);
        maxd=max(maxd,x-y);
        mind=min(mind,x-y);
        ans=max(ans,maxs-mins);
        ans=max(ans,maxd-mind);
    }
    printf("%d\n",ans);
    return 0;
}


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

int main() {
    vector<int>X(3);
  
    cin >> X.at(0) >> X.at(1) >> X.at(2);
  
  sort(X.begin(),X.end());
  
  int answer =X.at(2)*10+X.at(1)+X.at(0);
    cout << answer << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
//登録しよう！→ https://www.youtube.com/channel/UCRXsI3FL_kvaVL9zoolBfbQ
using namespace std;
using ll = long long;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}//a,bの最大公約数(gcd)を求める
ll lcm(ll a,ll b){return abs(a*b)/gcd(a,b);}//a,bの最小公倍数(lcm)を求める
vector<ll> enum_div(ll n){vector<ll> ret;for(int i=1 ; i*i<=n ; i++){if(n%i == 0){ret.push_back(i);if(i!=1 && i*i!=n)ret.push_back(n/i);}}ret.push_back(n);return ret;}
//↑nの約数を求める
vector<bool> IsPrime; void sieve(size_t max){if(max+1 > IsPrime.size())IsPrime.resize(max+1,true);IsPrime[0] = false;IsPrime[1] = false;for(size_t i=2; i*i<=max; ++i)if(IsPrime[i])for(size_t j=2; i*j<=max; ++j)IsPrime[i*j] = false;}
//↑エラトステネスの篩で素数を求める
#define roundup(divisor,dividend) (divisor + (dividend - 1)) / dividend //切り上げ割り算
#define all(x) (x).begin(),(x).end() //xの初めから終わりまでのポインタ
#define size_t ll //size_tは自動でllに変換される
#define pb(x) push_back(x)
#define gre greater //sortを降順にする
#define pri_queue priority_queue //優先度付きキュー
#define syo(x) fixed << setprecision(x) //iostreamで小数をx桁表示

void solve(long long N, std::vector<long long> A){
  map<ll,ll> x;
  ll y=0;
  vector<ll> com{0};
  ll sum = 0;
  for (int i = 1; i <= 2*100000; i++) {
    sum += i;
    com.pb(sum);
  }
 for (int i = 0; i < N; i++) {
   x[A[i]]++;
 } 
 for(auto itr = x.begin(); itr != x.end(); ++itr) {
   y += com[itr -> second -1];
 }
 for (int i = 0; i < N; i++) {
   cout << y - (x[A[i]]-1 >= 0 ? x[A[i]]-1 : 0)  << endl;
 }
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> A(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
    }
    solve(N, std::move(A));
}


Measured memory_bytes: 12912
N = int(input())
A = list(map(int,input().split()))

A.sort()
ans = 0
ans += A.pop()
i = 1
now =0
while i < N-1:
    now = A.pop()
    ans += now*2
    i += 2
if i > N-1:
    ans -= now
print(ans)


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

ll gcd(ll x,ll y)
{
    if(x==0)
        return y;
    return gcd(y%x,x);
}

ll power(ll x,ll y)
{
    ll res = 1;
    while(y>0){
        if(y&1)
            res *= x;
        y>>=1;
        x*=x;
    }
    return res;
}

void seive_prime(ll n)
{
    ll p[n+1]={0};
    for(ll i=2;i*i<=n;i++){
        if(p[i]==0){
            for(ll j=i*i;j<=n;j+=i){
                p[j]=1;
            }
        }
    }
    for(ll i=2;i<=n;i++)
        if(p[i]==0)
            cout<<i<<' ';
}
int main()
{
    string s[] = {"Sunny","Cloudy","Rainy",};
    string t;
    cin>>t;
    for(int i=0;i<3;i++){
        if(s[i]==t){
            cout<<s[(i+1)%3]<<'\n';
            return 0;
        }
    }
    return 0;
}


Measured memory_bytes: 256
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    s = sum(a[:k])
    m = s
    for i in range(n-k):
        s += a[i+k]-a[i]
        m = max(s, m)
    print((m+k)/2)


main()


Measured memory_bytes: 25060
#include <bits/stdc++.h>
#pragma gcc optimize("ofast")
using namespace std;

#define ll long long //data types used often, but you don't want to type them time by time
#define ull unsigned long long
#define ui unsigned int
#define mod 998244353
#define us unsigned short
#define IOS ios_base::sync_with_stdio(0); //to synchronize the input of cin and scanf
#define INF LONG_MAX
#define PI 3.1415926535897932384626
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define rep(x,j,n)for(int x=j;x<n;x++)
#define all(x) (x).begin(), (x).end()

typedef vector<pair<ll,ll>> vpi;
typedef vector<ll> vi;
typedef vector<vi> vvi;

bool prime(ll n)
{
    if(n<=1)return false;
    if(n<=3)return true;
    if(n%2==0||n%3==0)return false;
    for(ll i=5;i*i<=n;i+=6)
    {
        if(n%i==0||n%(i+2)==0)return false;
    }
    return true;
}

ll modexp(ll a,ll b,ll m)
{
    ll r=1;
    a=a%m;
    while(b>0)
    {
        if(b&1)r=(r*a)%m;
        b = b>>1;
        a=(a*a)%m;
    }
    return r%m;
}
bool comp(pair<ll,ll>a,pair<ll,ll>b)
{
    return a.fi>b.fi;
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
ll n,k; cin>>n>>k;
vi arr(n+1);

rep(i,0,k)
{
    ll d; cin>>d;
    rep(j,0,d)
    {
        ll x; cin>>x;
        arr[x]++;
    }
}
ll cnt = 0;
rep(i,1,n+1)if(arr[i]==0)cnt++;
cout<<cnt<<endl;
return 0;

}


Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0,i##_max=(N);i<i##_max;++i)
#define repp(i,l,r) for(int i=(l),i##_max=(r);i<i##_max;++i)
#define per(i,N) for(int i=(N)-1;i>=0;--i)
#define perr(i,l,r) for(int i=r-1,i##_min(l);i>=i##_min;--i)
#define all(arr) (arr).begin(), (arr).end()
#define SP << " " <<
#define SPF << " "
#define SPEEDUP cin.tie(0);ios::sync_with_stdio(false);
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

inline void YesNo(bool b){ cout << (b?"Yes" : "No") << endl;}
inline void YESNO(bool b){ cout << (b?"YES" : "NO") << endl;}
inline void Yay(bool b){ cout << (b?"Yay!" : ":(") << endl;}

int main(void){
  SPEEDUP
  cout << setprecision(15);
  int N;cin >> N;
  vector<ll> A(N);
  vector<ll> B(N);
  rep(i,N)cin >> A[i] >> B[i];
  ll count = 0;
  per(i,N){
    count += (B[i] - (A[i]+count)%B[i])%B[i];
  }
  cout << count << endl;
  return 0;
}


Measured memory_bytes: 1920
import math

def digits(num):
    return len(str(num))

N = int(input())
min_d = digits(N)
for i in list(range(2, math.ceil(math.sqrt(N)) + 1, 1)):
    if (N % i == 0):
        min_d = min(max(digits(i),digits(int(N / i))), min_d)
print(min_d)


Measured memory_bytes: 6900
def find(u, c, p, v):
    n = len(c)
    if not v[u]:
        v[u] = True
        for q in xrange(n):
            if c[u][q]:
                if p[q]==-1 or find(p[q], c, p ,v):
                    p[q] = u
                    return True
    return False

def maxMatch(c):
    foo = 0
    n = len(c)
    p = [-1 for i in xrange(n)]
    for i in xrange(n):
        v = [False for j in xrange(n)]
        if find(i, c, p, v):
            foo += 1
    return foo

def process(r, b):
    n = len(r)
    c = [[False for i in xrange(n)] for j in xrange(n)]
    for i in xrange(n):
        for j in xrange(n):
            if r[i][0]<b[j][0] and r[i][1]<b[j][1]:
                c[i][j] = True
    return maxMatch(c)

def main():
    n = int(raw_input().strip())
    r = []
    b = []
    for i in xrange(n):
        x, y = [int(sub) for sub in raw_input().strip().split()]
        r.append((x, y))
    for i in xrange(n):
        x, y = [int(sub) for sub in raw_input().strip().split()]
        b.append((x, y))
    print process(r, b)

if __name__=='__main__':
    main()


Measured memory_bytes: 2808
#include<iostream>
#include<map>
#include<queue>
using namespace std;
#define inRange(x, a, b) a <= x && x < b

int main(){
    int dx[4] = {-4, -1, 1, 4};
    map<string, int> m;
    queue<pair<string,int>> q;
    q.push({"01234567", 0});

    while(!q.empty()){
        pair<string,int> p = q.front(); q.pop();
        int times = p.second;

        if(m.count(p.first))    continue;

        m[p.first] = times;
        int zpos;
        for(zpos = 0;;zpos++) if(p.first[zpos] == '0')  break;

        for(int i = 0; i < 4; i++){
            int next = zpos + dx[i];
            if(min(next,zpos) == 3 && max(next,zpos) == 4)  continue;

            if(inRange(next, 0, 8)){
                swap(p.first[zpos], p.first[next]);
                if(m.count(p.first) == 0)   q.push({p.first, times+1});
                swap(p.first[zpos], p.first[next]);
            }
        }
    }

    string s;
    while(cin >> s){
        string t;
        for(int i = 0; i < 7; i++){
            cin >> t;
            s += t;
        }
        cout << m[s] << endl;
    }
    return 0;
}


Measured memory_bytes: 5388
use std::io;


fn main() {
    let (a, b) = {
        let i = read::<usize>();
        (i[0], i[1])
    };
    println!("{} {}", a * b, a * 2 + b * 2);
}


#[allow(dead_code)]
fn read<T>() -> Vec<T>
where T:
std::str::FromStr,
T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.split_whitespace()
        .map(|s| s.trim().parse().unwrap())
        .collect()
}

#[allow(dead_code)]
fn read_one<T>() -> T
where T:
std::str::FromStr,
T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim().parse().unwrap()
}


Measured memory_bytes: 5028
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  int cnt_a=0,cnt_w=0,cnt_t=0,cnt_r=0;
  for(int i=0;i<n;++i) {
    string s;
    cin >> s;
    if(s=="AC") cnt_a++;
    if(s=="WA") cnt_w++;
    if(s=="TLE") cnt_t++;
    if(s=="RE") cnt_r++;
  }
  cout << "AC" << " " << "x" << " " << cnt_a << endl;
  cout << "WA" << " " << "x" << " " << cnt_w << endl;
  cout << "TLE" << " " << "x" << " " << cnt_t << endl;
  cout << "RE" << " " << "x" << " " << cnt_r << endl;
}
    

Measured memory_bytes: 3616
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
#include <vector>
#include <set>
using namespace std;
const int maxn = 2e6+10;
typedef pair<int,int> pii;
typedef long long ll;

int N,K;
ll sum[maxn],arr[maxn];
int main(){
    cin>>N>>K;
    for(int i = 1;i<=N;i++){
        scanf("%lld",&arr[i]);
    }
    ll cur = 0,mx = 0;
    for(int i = 1;i<=N;i++){
        cur += arr[i];
        if(i>K) cur-=arr[i-K];
        if(i>=K) mx = max(mx,cur);

    }
    double res = (double)(K+mx)/2;
    printf("%.8lf\n",res);
    return 0;
}

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

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

  vector<int> perm1(N);
  vector<int> perm2(N);
  for(int i=0; i<N; i++){
    cin >> perm1.at(i);
  }
  for(int i=0; i<N; i++){
    cin >> perm2.at(i);
  }

  vector<int> buf(N);
  iota(buf.begin(), buf.end(), 1);
  int ord1= -1;
  int ord2= -1;
  int cnt= 1;
  do{
    bool match1= true;
    bool match2= true;
    for(int i=0; i<N; i++){
      if(perm1.at(i) != buf.at(i)){
        match1= false;
        break;
      }
    }
    for(int i=0; i<N; i++){
      if(perm2.at(i) != buf.at(i)){
        match2=  false;
        break;
      }
    }

    if(match1){ ord1= cnt; }
    if(match2){ ord2= cnt; }
    cnt++;
  } while(next_permutation(buf.begin(), buf.end()));

  int ans= abs(ord1- ord2);
  
  cout << ans << endl;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
#define pb push_back
using namespace std;

int vis[9];
vector <vector<int> > arr(10);
int cnt, N, M;
void dfs(int src)
{
    vis[src]=1;
    for(int j=0;j<arr[src].size();j++)
    {
        if(vis[arr[src][j]]==0)
            dfs(arr[src][j]);

    }
    cnt++;
    for(int i=1;i<=N;i++)
        if(vis[i]!=1)
        {
            cnt--;
            break;
        }
    //cout << src << " ";
    vis[src]=0;
}

int main()
{
    cin>>N>>M;
    cnt=0;
    memset(vis,0,sizeof vis);
    int x, y;
    for(int i=0;i<M;i++)
    {
        cin>>x>>y;
        arr[x].pb(y);
        arr[y].pb(x);
    }
    dfs(1);
    cout << cnt << endl;
    return 0;
}


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

int main() {
    int A, B;
    cin >> A >> B;
    int n = 0;
    for(int i = A; i <= B; i++){
        int x4, x3, x1, x0;
        int i0 = i;
        x0 = i0 % 10;
        i0 /= 10;
        x1 = i0 % 10;
        i0 /= 100;
        x3 = i0 % 10;
        i0 /= 10;
        x4 = i0 % 10;
        if(x0 == x4 && x1 == x3){
            n++;
        }
    }
    cout << n << endl;
}

Measured memory_bytes: 3632
#pragma GCC optimize("O3")

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for(int i = 0; i < (a); ++i)
#define pb push_back
#define sz size
#define f first
#define s second

int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, a, b;
    cin >> n >> a >> b;
    cout << min(n*a,b);

    return 0;
}


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

int main(void){
  int K;
  string S;
  cin >> K;
  cin >> S;
  int len = S.length();
  string sub = S.substr(0,K);
  if (len<=K) printf("%s\n",S.c_str());
  else printf("%s...\n",sub.c_str());
  return 0;
}

Measured memory_bytes: 3728
import java.util.*;
import java.lang.*;
import java.math.*;

public class Main {
	Scanner sc = new Scanner(System.in);
	void run(){
		for(;;){
			int n = sc.nextInt();
			
			if(n == 0){
				break;
			}
			int ans = 0;
			int data[] = new int[n];
			for(int i = 0; i < n ; i++){
				data[i] = sc.nextInt();
				for(int  j = 0 ; j < i; j++){
					if(data[i] < data[j]){
						ans+= 1;
					}
				}
			}
			System.out.println(ans);
			
		}
		
	}
	public static void main(String[] args){
		Main m = new Main();
		m.run();
	}
}

Measured memory_bytes: 12000
#include <stdio.h>
#include <string.h>
long double n;
long double dp[305][305][305];
long double recurs(int  n1,int n2,int n3)
{
	//printf("#%d %d %d\n",n1,n2,n3);
	if((n1<0 || n2<0 )|| n3<0) return 0;
	//printf("##%d %d %d\n",n1,n2,n3);
	if(dp[n1][n2][n3]!=-1) return dp[n1][n2][n3];
//	printf("1\n");
	long double k=n1+n2+n3;
	//printf("1\n");
		dp[n1][n2][n3]=(n/k)+((n1/k)*recurs(n1-1,n2,n3))+((n2/k)*recurs(n1+1,n2-1,n3))+((n3/k)*recurs(n1,n2+1,n3-1));
	//printf("##%d %d %d %0.8lf \n",n1,n2,n3,dp[n1][n2][n3]);
	return dp[n1][n2][n3];
}
int main()
{
	int n1=0,n2=0,n3=0;
	scanf("%Lf",&n);
	//memset(dp,-1,sizeof(dp));
	for(int i=0;i<=301;i++)
	{
		for(int j=0;j<=301;j++)
		{
			for(int t=0;t<=301;t++)
			{
				dp[i][j][t]=-1;
			}
		}
	}
	dp[0][0][0]=0;
	for(int i=0;i<n;i++)
	{
		int x;
		scanf("%d",&x);
		if(x==1) n1++;
		else if(x==2) n2++;
		else n3++;
	}
//	printf("%d %d %d\n",n1,n2,n3);
//	printf("2\n");
	long double ans=recurs(n1,n2,n3);
	printf("%0.9Lf\n",ans);
	return 0;
}


Measured memory_bytes: 440576
#include <bits/stdc++.h>
#define lid (id<<1)
#define rid (id<<1|1)
using namespace std;

typedef long long LL;
const int N = 1e2 + 10;

int n;
char s[N];
int min_x[N],f[N],sum = 0;
int p[N];

bool cmp(int i,int j)
{
    if(min_x[p[i]] == 0)
    {
        return true;
    }
    if(min_x[p[j]] == 0)
    {
        return false;
    }

    if(f[p[i]] >= 0)
    {
        if(f[p[j]] < 0 || min_x[p[i]] > min_x[p[j]])
          return true;
        else
          return false;
    }

    if(f[p[j]] >= 0)
    {
        return false;
    }

    return true;
}

int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)
    {
        int l;
        scanf("%s",s + 1);
        l = strlen(s + 1);
        f[i] = 0;min_x[i] = 0;
        for(int j = 1;j <= l;j++)
        {
            f[i] += s[j] == '(' ? 1 : -1;
            min_x[i] = min(min_x[i],f[i]);
        }
        sum += f[i];
  //      cout<<f[i]<<" "<<min_x[i]<<endl;
    }
    if(sum != 0)
    {
        printf("No\n");
        return 0;
    }

    int tot = 0;
    bool use[N];
    memset(use,0,sizeof(use));

    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= n;j++)
        {
            if( (min_x[j] == 0 && !use[j]) || (f[j] >= 0 && tot + min_x[j] >= 0 && !use[j]) )
            {
                tot+=f[j];
                use[j] = true;
            }
        }
    }

    int f1[N],f2[N],m = 0,cm = 0;
    for(int i = 1;i <= n;i++)
    if(!use[i])
    {
        if(f[i] >= 0)
        {
            printf("No\n");
            return 0;
        }
        m++;
        f1[m] = -1 * f[i];
        f2[m] = -1 * min_x[i];
    }

    int now = 0;
    for(int i = 1;i <= m;i++)
    {
        for(int j = 1;j <= m;j++)
        {
            if(now + f1[j] >= f2[j])
            {
                now += f1[j];
                f2[j] = 10000;
            }
        }
    }

    if(tot == now) printf("Yes\n");
    else printf("No\n");

	return 0;
}

Measured memory_bytes: 3116
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int main(){
    string str;
    int JOI, IOI;
    while(cin>>str){
        JOI = 0; IOI = 0;
        for(int i = 0; i < str.size() - 2;i++){
            if(str[i] == 'J' && str[i+1] == 'O' && str[i+2] == 'I') JOI++;
            else if(str[i] == 'I' && str[i+1] == 'O'&& str[i+2] == 'I') IOI++;
        }
        printf("%d\n",JOI);
        printf("%d\n",IOI);
    }
    return 0;
}



Measured memory_bytes: 3116
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
int main(){
#define int long long int
    int n;cin>>n;
    int a[n];for(int i=0;i<n;i++)cin>>a[i];
    vector<int> v;
    int t=1;
    for(int i=0;i<n;i++){
        if(a[i]==t){v.pb(i);t++;}
    }
    if(v.size()==0)cout<<-1;
    else cout<<(n-v.size());
    return 0;
}

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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define ALL(a) (a).begin(), (a).end()
#define rALL(a) (a).rbegin(), (a).rend()
#define SZ(x) ((int)(x).size())
using ll = long long;
using ull = unsigned long long;
using P = pair<int, int>;
using llP = pair<ll, ll>;
using DoP = pair<double, double>;
const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int INF = 1 << 28;
const ll INF64 = 1ll << 55;
const int mod = 1000000007;
//const int mod = 998244353;

template <class T>inline bool chmin(T &a, const T b)
{
  if (a > b)
  {
    a = b;
    return true;
  }
  return false;
}
template <class T>inline bool chmax(T &a, const T b)
{
  if (a < b)
  {
    a = b;
    return true;
  }
  return false;
}
template <class T>inline void line_out(const vector<T> vec) {
  int n = SZ(vec);
  rep(i, n) {
    cout << vec[i];
    if(i < n-1) cout << " ";
  }
  cout << endl;
  return;
}

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

  // for prime mod
  mint inv() const
  {
    return pow(mod - 2);
  }
  mint &operator/=(const mint a)
  {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const
  {
    mint res(*this);
    return res /= a;
  }
};

int main()
{
  int m;
  cin >> m;
  cout << 48-m << endl;
}

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

int main() {
  string S;
  cin >> S;
  int num = S.size();
  if(S[num-1] == 's'){
    S.push_back('e');
    S.push_back('s');
  }else{
    S.push_back('s');
  }
  cout << S;
  return 0;
}

Measured memory_bytes: 3624
using System;
using System.Collections.Generic;
using System.Text;
using System.Numerics;
using System.IO;

namespace SolutionCS
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());

            int[] c = new int[26];
            int[] t = new int[26];
            for (int i = 0; i < c.Length; i++)
            {
                c[i] = int.MaxValue;
            }

            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < 26; j++)
                {
                    t[j] = 0;
                }

                string s = Console.ReadLine();
                for (int j = 0; j < s.Length; j++)
                {
                    t[s[j] - 'a']++;
                }

                for (int j = 0; j < 26; j++)
                {
                    c[j] = Math.Min(c[j], t[j]);
                }
            }

            for (int i = 0; i < 26; i++)
            {
                for (int j = 0; j < c[i]; j++)
                {
                    Console.Write("{0}", (char)(i + 'a'));
                }
            }

            Console.WriteLine();
        }
    }
}


Measured memory_bytes: 11220
#include <iostream>
#include <fstream>
#include <string> 
#include <cstring>
#include <cmath>  
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <functional>
#include <cctype>
#include <list>
//#include <boost/multiprecision/cpp_int.hpp>

#define BIT(a) (1 << (a))
#define EPS (1e-10)

using namespace std;
//using namespace boost::multiprecision;

const long long MOD = 1000000007;
const int COUNTER_CLOCKWISE = 1;
const int CLOCKWISE = -1;
const int ONLINE_BACK = 2;
const int ONLINE_FRONT = -2;
const int ON_SEGMENT = 0;

class Point{
    public:
    double x, y;

    Point(double x = 0, double y = 0): x(x), y(y) {}
    
    Point operator+(Point p){return Point(x + p.x, y + p.y);}
    Point operator-(Point p){return Point(x - p.x, y - p.y);}
    Point operator*(double a){return Point(a * x, a * y);}
    Point operator/(double a){return Point(x / a, y / a);}

    bool operator < (const Point &p) const {
        return y != p.y ? y < p.y : x < p.x;
    }

    double norm(){return x * x + y * y;}
};
typedef Point Vector;
typedef vector<Vector> Polygon;

double cross(Vector a, Vector b){
    return a.x*b.y - a.y*b.x;
}

double dot(Vector a, Vector b){
    return a.x * b.x + a.y * b.y;
}

int ccw(Point p0, Point p1, Point p2){
    Vector a = p1 - p0;
    Vector b = p2 - p0;
    if (cross(a, b) > EPS)return COUNTER_CLOCKWISE;
    if (cross(a, b) > -EPS)return CLOCKWISE;
    if (dot(a, b) < -EPS)return ONLINE_BACK;
    if (a.norm() < b.norm())return ONLINE_FRONT;

    return ON_SEGMENT;
}

Polygon andrewScan(Polygon s){
    Polygon u, l;
    if (s.size() < 3) return s;
    sort(s.begin(), s.end());
    u.push_back(s[0]);
    u.push_back(s[1]);
    l.push_back(s[s.size()-1]);
    l.push_back(s[s.size()-2]);
    
    for (size_t i = 2; i < s.size(); i++){
        for (size_t n = u.size(); n >= 2 && ccw(u[n-2], u[n-1], s[i]) == COUNTER_CLOCKWISE; n--){
            u.pop_back();
        }
        u.push_back(s[i]);
    }

    for (int i = (int)s.size() - 3; i >= 0; i--){
        for (size_t n = l.size(); n >= 2 && ccw(l[n-2], l[n-1], s[i]) == COUNTER_CLOCKWISE; n--){
            l.pop_back();
        }
        l.push_back(s[i]);
    }

    reverse(l.begin(), l.end());
    for (size_t i = u.size() - 2; i >= 1; i--) l.push_back(u[i]);

    return l;
}

long long mod_pow(long long x, long long n){
    long long res = 1;
    for(int i = 0;i < 60; i++){
        if(n >> i & 1) res = res * x % MOD;
        x = x * x % MOD;
    }
    return res;
}

int a[10000];

int main(void){
    int K, T;
    cin >> K >> T;
    int ma = 0;
    int sum = 0;
    for (int i = 0; i < T; i++){
        cin >> a[i];
        ma = max(ma, a[i]);
        sum += a[i]; 
    }
    sum -= ma;
    cout << (ma-sum-1 < 0 ? 0 : ma-sum-1) << endl;

    return 0;
}   


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


void solve(long long N){
  long long sum = 0;
  for (long long i=1; i<=N; i++) if (i%3 != 0 && i%5 != 0) sum += i;
  cout << sum << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    solve(N);
    return 0;
}


Measured memory_bytes: 3656
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
#define rep(i, begin, n) for (int i = begin; i < n; i++)
#define repe(i, begin, n) for (int i = begin; i <= n; i++)
#define repr(i, begin, n) for (int i = begin; i > begin - n; i--)
#define repre(i, begin, end) for (int i = begin; i >= end; i--)

template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

template <class T>
inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}

const int inf = 1000000007;
const int MOD = 1000000007;
const long long INF = 1000000000000000007;

// -------------------------------------------------------

string S;
string days[] = {"SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"};

int main() {
  cin >> S;
  rep(i, 0, 7) {
    if (S == days[i]) {
      cout << 7 - i << endl;
      return 0;
    }
  }
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
template<class T> ostream& operator<<(ostream &os, vector<T> V) {
os << "[ "; for(auto v : V) os << v << " "; return os << "]";}
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P) {
    return os << "(" << P.first << "," << P.second << ")";}

// #define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...) 1
#endif
typedef long long ll;
typedef double ld;
#define pll pair<ll,ll>
#define pii pair<int, int>
#define pb push_back
#define mp(x, y) make_pair((x), (y))
#define F first
#define S second
#define I insert
#define vi vector<int>
#define vll vector<ll>
#define vpll vector<pll>
#define all(x) (x).begin(), (x).end()
#define sz(x) (ll)(x).size()
   
const ll Mod = 1e9 + 7;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
    ll W , H , x , y;
    cin >> W >> H >> x >> y;
    double ans = (double)(W*H)/2;
    if(2*x == W  && 2*y == H)
        printf("%0.15lf 1\n" , ans);
    else
        printf("%0.15lf 0\n" , ans);
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

#define N 30
#define INF 10000
int w, h;
int s[N][N];
int c[4];

struct point{
    int x, y;
};

bool invalid(int x, int y){
    return (x < 0 || x >= w || y < 0 || y >= h);
}

int dijkstra(){
    int d[N][N][4];
    int used[N][N][4];
    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};
    
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            for (int k = 0; k < 4; k++) {
                d[i][j][k] = INF;
                used[i][j][k] = false;
            }
        }
    }
    
    d[0][0][0] = 0;
    
    while (true) {
        int p;
        point v;
        v.x = -1; v.y = -1;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                for (int k = 0; k < 4; k++) {
                    if (!used[i][j][k] && ((v.x == -1 && v.y == -1) || d[i][j][k] < d[v.y][v.x][p])) {
                        v.y = i; v.x = j; p = k;
                    }
                }
            }
        }
        
        if (v.x == -1 && v.y == -1) {
            break;
        }
        
        used[v.y][v.x][p] = true;

        for (int i = 0; i < 4; i++) {
            int mx = v.x + dx[i];
            int my = v.y + dy[i];
            if (invalid(mx, my)) {
                continue;
            }
            
            if (s[v.y][v.x] != 4 && i == (p + s[v.y][v.x]) % 4) {
                d[my][mx][i] = min(d[my][mx][i], d[v.y][v.x][p]);
            }
            else{
                int k = -1;
                for (int j = 0; j < 4; j++) {
                    if (i == (p + j) % 4) {
                        k = j;
                        break;
                    }
                }
                d[my][mx][i] = min(d[my][mx][i], d[v.y][v.x][p] + c[k]);
            }
        }
    }
    
    int ans = INF;
    for (int i = 0; i < 4; i++) {
        ans = min(ans, d[h - 1][w - 1][i]);
    }
    return ans;
}



int main()
{
    while (true) {
        cin >> w >> h;
        if (w == 0 && h == 0) {
            break;
        }
        
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin >> s[i][j];
            }
        }
        
        for (int i = 0; i < 4; i++) {
            cin >> c[i];
        }
        cout << dijkstra() << endl;
    }
    return 0;
}

Measured memory_bytes: 1188
n = int(input())
t, a = map(int, input().split())
h = list(map(int, input().split()))

ans = 0
l = a + 10000

for i in range(n):
    k = abs(t-h[i]*0.006-a)
    if l > k:
        l = k
        ans = i+1

print(ans)

Measured memory_bytes: 9200
A = [[int(i) for i in input().split()] for i in range(3)]
ans = 'Yes'

for i in range(2):
    if A[i][0] - A[i + 1][0] != A[i][1] - A[i + 1][1]:
        ans = 'No'
        break
    if A[i][1] - A[i + 1][1] != A[i][2] - A[i + 1][2]:
        ans = 'No'
        break
        
print(ans)

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();

		if (N%2 == 0) {
			System.out.println(N);
		} else {
			System.out.println(N*2);
		}
	}
}


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

static const int Maxn = 100005;

int n, st, ed;
char op[Maxn];
long long a[Maxn];
long long dp[Maxn][3];

int main() {
  scanf("%d\n", &n);
  scanf("%lld ", a + 1), op[1] = '+';
  for (int i = 2; i <= n; ++i)
    scanf("%c %lld ", op + i, a + i);
  memset(dp, -63, sizeof(dp));
  dp[0][0] = 0;
  for (int i = 1; i <= n; ++i) {
    dp[i][2] = dp[i - 1][2] + a[i];
    if (op[i] == '-') {
      dp[i][1] = max(dp[i - 1][0] - a[i], dp[i - 1][1] + a[i]);
      dp[i][2] = max(dp[i][2], dp[i - 1][1] + a[i]);
    }
    else {
      dp[i][0] = max(dp[i - 1][0] + a[i], dp[i - 1][1] + a[i]);
      dp[i][1] = max(dp[i - 1][2] + a[i], dp[i - 1][1] - a[i]);
    }
  }
  printf("%lld\n", max(dp[n][0], max(dp[n][1], dp[n][2])));
  return 0;
}

Measured memory_bytes: 3456
#![allow(non_snake_case)]
fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let N:usize = sc.read();
    let mut X:i64 = sc.read();
    let mut D:i64 = sc.read();
    if D == 0{
        if X == 0{
            println!("1");
        }else{
            println!("{}", N+1);
        }
        return
    }
    if D < 0{
        X = -X;
        D = -D;
    }
    let mut map = std::collections::BTreeMap::<i64, Vec<(i64, i64)>>::new();
    for k in 0..(N+1){
        let t = k as i64;
        let tX = X*t;
        let minimum = tX/D + t*(t-1)/2;
        let maximum = tX/D + ((N as i64)*t - t*(t+1)/2);
//        println!("{} {} tX{} {} {}",N ,t ,tX/D,t*(t+1)/2 , ((N as i64)*t - t*(t+1)/2));
        let corresponding_vector = map.entry(tX%D).or_insert(vec![]);
        corresponding_vector.push((minimum, maximum));
    }

    let mut ans = 0;
    for (_,a) in map{
        let mut a = a;
        a.sort();
        let mut first = a[0].0;
        let mut second = a[0].1;
        for i in 1..a.len(){
//            println!("{} {}", a[i].0, a[i].1);
            if second < a[i].0{
                ans += second - first + 1;
                first = a[i].0;
                second = a[i].1;
            }else if second < a[i].1{
                second = a[i].1;
            }
        }
        ans += second - first + 1;
    }

    println!("{}", ans);

}

pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n')
            .take_while(|&b| b != b' ' && b != b'\n')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
        .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}




Measured memory_bytes: 37116
/*    特徴    */

/*    教訓    */

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

using ll = long long;
using ld  = long double;
using pint = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
const int INF=1e9+7;
const ll LINF=9223372036854775807;
const ll MOD=1e9+7;
const ld PI=acos(-1);
const ld EPS = 1e-9; //微調整用（EPSより小さいと0と判定など）

int ii() { int x; if (scanf("%d", &x) == 1) return x; }
long long il() { long long x; if (scanf("%lld", &x) == 1) return x; }
string is() { string x; cin >> x; return x; }
char ic() { char x; cin >> x; return x; }
void oi(int x) { printf("%d ", x); }
void ol(long long x) { printf("%lld ", x); }
void od_nosp(double x) { printf("%.15f", x); } // 古い問題用
void od(double x) { printf("%.15f ", x); }
// long doubleで受け取り、fをLfなどに変えて出力すると、変な数値が出る
// それをなんとかするには独自の出力を作らなければならなそう
void os(const string &s) { printf("%s ", s.c_str()); }
void oc(const char &c) { printf("%c ", c); }
#define o_map(v){cerr << #v << endl; for(const auto& xxx: v){cout << xxx.first << " " << xxx.second << "\n";}} //動作未確認
void br() { putchar('\n'); }

#define gcd __gcd //llは受け取らない C++17~のgcdと違うので注意
int lcm(int a, int b){return a / gcd(a, b) * b;}
#define begin_end(a) a.begin(),a.end() //sort(begin_end(vec));
#define REP(i,m,n) for(ll i=(ll)(m) ; i < (ll) (n) ; i++ )
#define rep(i,n) REP(i,0,n)
#define m_p(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define p_b push_back
#define SZ(x) ((int)(x).size) //size()がunsignedなのでエラー避けに

//4近傍（上下左右） rep(i, 2) にすると右・下だけに進む
vector<int> dx_4 = {1, 0, -1, 0};
vector<int> dy_4 = {0, 1, 0, -1};

// coutによるpairの出力（空白区切り）
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << " " << p.second << ")";}
// coutによるvectorの出力（空白区切り）
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size();
  for (int i = 0; i < len; ++i) {
    s << v[i]; if (i < len - 1) s << " "; //"\t"に変えるとTabで見やすく区切る
  }
  return s;
}
// coutによる多次元vectorの出力（空白区切り）
template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
  int len = vv.size();
  for (int i = 0; i < len; ++i) {
    s << vv[i] << endl;
  }
  return s;
}

//最大値、最小値の更新。更新したor等しければtrueを返す
template<typename T>
bool chmax(T& a, T b){return (a = max(a, b)) == b;}
template<typename T>
bool chmin(T& a, T b){return (a = min(a, b)) == b;}

// -------- template end - //


// - library ------------- //

 

// --------- library end - //


// - main() -------------- //

int main(){


  ll n = il();

  ll max_a = 0;
  vector<ll> as;
  rep(i, n){
    ll a = il();
    as.p_b(a);
  }

  sort(begin_end(as));
  reverse(begin_end(as));

  max_a = as[0];
  as.erase(as.begin());

  ll ideal_aj = 1000000000000;
  for (ll a : as){
    if (abs(max_a - a - a) <= abs(max_a - ideal_aj - ideal_aj)) ideal_aj = a;
  }

  ol(max_a); ol(ideal_aj); br();

// ---------- main() end - //
}

Measured memory_bytes: 1400
#include<cstdio>
#include<cmath>
int n;
int a[100005];
int cnt[2][100005];
int max[2],max2[2], x[2],x2[2];
int pro(int start) {
	int i;
	for (i = start; i < n; i += 2) {
		cnt[start][a[i]]++;
	}
	for (i = 1; i <= 100000; i++) {
		if (max[start] < cnt[start][i]) {
			max2[start] = max[start];
			x2[start] = x[start];
			max[start] = cnt[start][i];
			x[start] = i;
		}
		else if (max2[start] < cnt[start][i]) {
			max2[start] = cnt[start][i];
			x2[start] = i;
		}
	}
	return 0;
}
int main() {
	scanf("%d", &n);
	int i;
	for (i = 0; i < n; i++) scanf("%d", &a[i]);
	pro(0);
	pro(1);
	int sub;
	if (x[0] != x[1]) sub = max[0] + max[1];
	else {
		if (max[0] + max2[1] > max[1] + max2[0]) sub = max[0] + max2[1];
		else sub = max[1] + max2[0];
	}
	printf("%d", n - sub);
	return 0;
}

Measured memory_bytes: 1280
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <iostream>
#include <fstream>
#include <numeric>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <cmath>
#include <set>
#include <map>
#include <functional>
#include <bitset>
#include <iomanip>
#include <stack>
#include <list>
using namespace std;
#define ll           long long
#define all(v)       (v).begin() , (v).end()
#define vi           vector <ll>
#define vii          vector <pair<ll,ll>>
#define ii           pair<ll,ll>
#define sz(v)	     ((int)((v).size()))
#define lp(i,a,b)    for(int i=a;i<b;i++)
#define pb           push_back
#define pf           push_front
#define F            first
#define S            second
#define endl         "\n"
#define IOS          ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const double PI = 3.14159265358979323846;
const ll inf=2e9,MOD=1e9+7,MAX=1e5+1;

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int res=0;
    string s,t;
    cin>>s>>t;
    lp(i,0,sz(s))
        res+=(s[i]!=t[i]);
    cout<<res;
}

Measured memory_bytes: 3892