akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod = 1000000007;
ll mul(ll a, ll b){
    return ((a%mod) * (b%mod))%mod;
}
ll power(ll a, ll b){
    ll z = 1; ll x = a;
    while(b>0){
        if (b&1)z = mul(z, x);
        x = mul(x, x);
        b >>= 1;
    }
    return z;
}
int main()
{
    ll n, k;
    cin>>n>>k;
    ll ans  = 0;
    ll a[n]; for (int i=0; i<n; i++)cin>>a[i];
    ll k1[n] = {0}, k2[n]={0};
    for (int i=0; i<n; i++){
        for (int j=i-1; j>=0; j--)if (a[i]>a[j])k2[i]++;
        for (int j=i+1; j<n; j++)if (a[i] > a[j])k1[i]++;
    }
    for (int i=0; i<n; i++){
        ans += (mul(k1[i], k*(k+1)/2) + mul(k2[i], k*(k-1)/2))%mod;
    }
    // ans %= mod;
    // ll x = k*(k+1)/2; x %= mod;
    // ans = mul(ans, x);
    ans %= mod;
    cout<<ans<<endl;
}

Measured memory_bytes: 3652
//#include <ext/pb_ds/assoc_container.hpp> 
    // #include <ext/pb_ds/tree_policy.hpp> 
    #include <iostream>
    #include <iomanip>
    #include <sstream>
    #include <cstring>
    #include <vector>
    #include <deque>
    #include <queue>
    #include <set>
    #include <map>
    #include <valarray>
    #include <iterator>
    #include <functional>
    #include <limits>
    #include <algorithm>
    #include <numeric>
    #include <cmath>
    #include <cassert>
    #include <unordered_map>
    #include <unordered_set>
    #include <stack>
    using namespace std;
    #define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    #define trace(x) cerr << #x << ": " << x << " " << endl;
     
    typedef int64_t ll;
     
    #define endl '\n'
    #define int ll
    ll mod=1e17;
    ll mod1=1e9+5;
     
    ll power(ll a,ll b)
    {
        if(b==0) return 1;
        else if(b%2==0)
            return power((((a%mod)*(a%mod))%mod),b/2)%mod;
        else return ((a%mod)*(power((((a%mod)*(a%mod))%mod),b/2)%mod))%mod;
    }
     
    // using namespace __gnu_pbds;
    // #define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update>
    //find_by_order(k)  returns iterator to kth element starting from 0;
    //order_of_key(k) returns count of elements strictly smaller than k;
    //erase,insert same as normal set
  
    int32_t main()
    {
        IOS
   
        
       int h;
       cin>>h;
       set<int> m;
       m.insert(h);
       unordered_map<int,int> m1;
       int ans=0;
       m1[h]++;

       while(h)
       {
        ans++;
        h/=2; 
       }
       cout<<2*(power(2,ans-1)-1)+1<<endl;


    }       

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)

ll gcd(ll p,ll q){for(ll t;q;)t=p%q,p=q,q=t;return p;}


//sからtへの最大流 O(E flow)を横着してO(VV flow)
//*
#define VMAX 1010
int vcnt;
int foodoflag[VMAX];
int resflow[VMAX][VMAX];

int foododfs(int s,int t){
	if(s==t)return 1;
	foodoflag[s]=1;
	rep(i,0,vcnt)if(!foodoflag[i]&&resflow[s][i]>0){
		if(foododfs(i,t)){
			resflow[s][i]--;
			resflow[i][s]++;
			return 1;
		}
	}
	return 0;
}
int foodo(int s,int t){
	int ans=0;
	rep(i,0,vcnt)foodoflag[i]=0;
	while(foododfs(s,t)){
		ans++;
		rep(i,0,vcnt)foodoflag[i]=0;
	}
	return ans;
}
#undef VMAX
//*/

int a[510],b[510];
int main(){
	int n,m;
	while(scanf("%d%d",&n,&m),n){
		rep(i,0,n)scanf("%d",a+i);
		rep(j,0,m)scanf("%d",b+j);
		vcnt=n+m+2;
		rep(i,0,vcnt)rep(j,0,vcnt)resflow[i][j]=0;
		rep(i,0,n)resflow[0][i+1]=1;
		rep(j,0,m)resflow[j+n+1][m+n+1]=1;
		rep(i,0,n)rep(j,0,m)if(gcd(a[i],b[j])!=1)resflow[i+1][j+n+1]=1;
		printf("%d\n",foodo(0,n+m+1));
	}
}


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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define forn(i,n) for(int i=0;i<int(n);++i)
#define vet(a) for(auto&i:a)cout<<i<<" "
#define out(a) cout<<a<<endl

typedef long long int ll;

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

	int n;
	cin>>n;
	int lowest=1000;
	while(lowest<n){
		lowest+=1000;
	}
	cout<<lowest-n<<endl;


	return 0;
}

Measured memory_bytes: 3660
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;


int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    auto ok = [&](int x) {
        int d = x % 10;
        while (x != 0) {
            if (d != x % 10) {
                return false;
            }
            x /= 10;
        }
        return true;
    };
    while (true) {
        if (ok(n)) {
            break;
        }
        ++n;
    }
    cout << n << '\n';

    return 0;
}

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

void main(string[] args)
{
    string s = readln.strip;
    string t = readln.strip;

    long cnt = 0;
    foreach (i; 0 .. s.length)
    {
        if (s[i] != t[i])
        {
            cnt++;
        }
    }
    writeln(cnt);
}


Measured memory_bytes: 3024
a = []
for _ in range(3):
    a.append(list(map(int,input().split()))) 
n = int(input())
num_list = []
for _ in range(n):
    num_list.append(int(input()))
    
flg = False
for i in range(3):
    if a[i][0] in num_list and a[i][1] in num_list and a[i][2] in num_list:
        flg = True
        break
        
for i in range(3):
    if a[0][i] in num_list and a[1][i] in num_list and a[2][i] in num_list:
        flg = True
        break
        
if flg != True:
    diago = list([a[0][0],a[1][1],a[2][2]])
    if diago[0] in num_list and diago[1] in num_list and diago[2] in num_list:
        flg = True
        
if flg != True:
    diago2 = list([a[2][0],a[1][1],a[2][0]])
    if diago2[0] in num_list and diago2[1] in num_list and diago2[2] in num_list:
        flg = True
        
if flg:
    print("Yes")
else:
    print("No")

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

using namespace std;

#define cerr if(false)cerr
#define what(x) cerr<<#x<<" = "<<x<<endl
 
typedef int ll;
typedef pair<ll, ll> ii;

const int maxN = 1e6 + 9, maxV = 1e6 + 9, MOD = 1e9 + 7, SQ = 322;
const int INF = 1e9;
vector<ii> diff;
ii segment[4 * maxN];
int n;

void build(int node, int left, int right){
	if(left == right){
		segment[node] = {diff[left].first, left};
	}else{
		int mid = (left + right) / 2;
		build(2 * node, left, mid);
		build(2 * node + 1, mid + 1, right);
		segment[node] = max(segment[2*node], segment[2*node+1]);
	}
}

ii query(int node, int curl, int curr, int l, int r){
	if(curr < l || curl > r) return {-INF, -INF};
	if(l <= curl && curr <= r) return segment[node];
	int mid = (curr + curl) / 2;
	return max(query(2 * node, curl, mid, l , r), query(2*node+1, mid+1, curr, l, r));
}

int SearchPos(ll x){
	int left = 0;
	int right = n-1;
	int pos = -1;
	while(left <= right){
		int mid = (left + right) / 2;
		if(diff[mid].second < x){
			left = mid + 1;
		}else{
			pos = mid;
			right = mid - 1;
		}
	}
	return pos;
}

void update(int node, int left, int right, int pos, int val){
	if(left == right){
		segment[node] = {val, pos};
	}else{
		int mid = (left + right) / 2;
		if(pos <= mid)
			update(2*node, left, mid, pos, val);
		else
			update(2*node+1, mid+1, right, pos, val);
		segment[node] = max(segment[2*node], segment[2*node+1]);
	}
}

int main(){

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

	cin >> n;

	diff.assign(n, {0,0});

	string s;
	int diffe = 0;
	for(int i = 0 ; i < n; i++){
		cin >> s;
		diffe = 0;
		for(int j = 0 ; j < s.size(); j++){
			diffe += (s[j] == '(' ? 1 : -1);
			diff[i].first += (s[j] == '(' ? 1 : -1);
			diff[i].first = max(0, diff[i].first);
			diff[i].second = min(diffe, diff[i].second);
		}
	}

	sort(diff.begin(), diff.end(), [](const ii& a, const ii& b){
		if(a.second == b.second)return a.first < b.first;
		return a.second < b.second;
	});

	build(1, 0, n-1);

	ll cur_dif = 0;
	int pos;
	for(int i = 0; i < n; i++){
		pos = SearchPos(-cur_dif);
		if(pos == -1){
			cout << "No" << endl;
			return 0;
		}
		auto it = query(1, 0, n-1, pos, n-1);
		cur_dif += it.first + diff[it.second].second;
		update(1, 0, n-1, it.second, -INF);
		if(cur_dif < 0){
			cout << "No" << endl;
			return 0;
		}
	}

	cout << (cur_dif == 0 ? "Yes" : "No") << endl;

	return 0;
}

Measured memory_bytes: 27380
import Control.Applicative ((<$>), (<*>))
import Control.Monad
import Data.List

main :: IO ()
main = do
  ps <- getLine
  unless (ps == "#") $ do
    putStrLn $ solve ps
    main

solve :: String -> String
solve = g . (== 'B') . (foldl f 'A')
  where
    f 'D' _ = 'D'
    f 'A' '0' = 'X'
    f 'A' '1' = 'Y'
    f 'X' '0' = 'D'
    f 'X' '1' = 'Z'
    f 'Y' '0' = 'X'
    f 'Y' '1' = 'D'
    f 'Z' '0' = 'W'
    f 'Z' '1' = 'B'
    f 'W' '0' = 'B'
    f 'W' '1' = 'Y'
    f 'B' '0' = 'Y'
    f 'B' '1' = 'X'
    g True = "Yes"
    g False = "No"

Measured memory_bytes: 3716
#include <iostream>
#include <vector>

using lli = long long int;
std::vector<lli> vec;
int main() {
    int n;
    std::cin >> n;
    vec.assign(n+1, 0);
    vec[0] = 1;
    vec[1] = 1;
    for (int i = 2; i <= n; i++) {
        vec[i] = vec[i-1] + vec[i-2];
    }
    std::cout << vec[n] << std::endl;

}



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

namespace Practice
{
    class Program
    {
        static void Main(string[] args)
        {
            SolveA();
            //SolveB();
            //SolveC();
            //SolveD();
        }
        private const long MOD = 1000000007;
       
        static void SolveA()
        {
            var o = ReadAndParseIntArr();
            int a = o[0];
            int b = o[1];
            int t = a + b;
            if( t % 2 == 0)
            {
                Console.WriteLine(t / 2);
            }
            else
            {
                Console.WriteLine(t / 2 + 1);
            }
        }

        #region よく使う便利関数
        private static bool isPrime(long x)
        {
            if( x == 2) { return true; }
            if( x < 2 || x % 2 == 0) { return false; }
            long i = 3;
            while( i * i <= x)
            {
                if( x % i == 0) { return false; }
                i = i + 2;
            }
            return true;
        }
        private static long lcm(long x, long y)
        {
            return x / gcd(x, y) * y;
        }
        private static long gcd(long x, long y)
        {
            return y > 0 ? gcd(y, x % y) : x;
        }

        private static int ReadAndParseInt()
        {
            return int.Parse(Console.ReadLine());
        }
        private static int[] ReadAndParseIntArr()
        {
            return Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
        }
        private static long ReadAndParseLong()
        {
            return long.Parse(Console.ReadLine());
        }
        private static long[] ReadAndParseLongArr()
        {
            return Array.ConvertAll(Console.ReadLine().Split(' '), long.Parse);
        }
        #endregion
    }
}

Measured memory_bytes: 11092
from collections import Counter
from itertools import combinations

N = int(input())
L = list(map(int, input().split()))
C = Counter(L)

def can_triangle(d):
    d.sort()
    a, b, c = d
    return a+b > c


def solve():
    ans = 0
    for c in combinations(C.keys(), 3):
        if can_triangle(list(c)):
            ans += C[c[0]]*C[c[1]]*C[c[2]]
    return ans

if __name__ == "__main__":
    print(solve())


Measured memory_bytes: 9476
#include <cstdio>
#include <vector>
using namespace std;
const int MAXN = 1005;
const int inf = 1e9;
vector<int> adj[MAXN];
int n, x[MAXN];
int f[MAXN][2];
int g[MAXN][MAXN * 5];
void dfs(int u) {
    for(int i = 0; i < adj[u].size(); i++) dfs(adj[u][i]);
    for(int k = 0; k < 2; k++) {
        for(int i = 1; i <= adj[u].size(); i++) {
            int v = adj[u][i - 1];
            for(int j = 0; j <= x[u]; j++) {
                g[i][j] = inf;
                if(x[v] <= j) g[i][j] = std::min(g[i][j], g[i - 1][j - x[v]] + f[v][k]);
                if(f[v][k ^ 1] <= j) g[i][j] = std::min(g[i][j], g[i - 1][j - f[v][k ^ 1]] + x[v]);
            }
        }
        f[u][k] = g[adj[u].size()][x[u]];
    }
}
int main() {
    scanf("%d", &n);
    for(int i = 2; i <= n; i++) {
        int p; scanf("%d", &p);
        adj[p].push_back(i);
    }
    for(int i = 1; i <= n; i++) scanf("%d", &x[i]);
    dfs(1);
    if(f[1][0] < inf || f[1][1] < inf) printf("POSSIBLE\n");
    else printf("IMPOSSIBLE\n");
    return 0;
}

Measured memory_bytes: 17280
using System;
using System.Linq;

class prog{
  static void Main(){
    
    string[] input = Console.ReadLine().Split().ToArray();
    Console.WriteLine(input[0][input[0].Length-1] == input[1][0]&&input[1][input[1].Length-1] == input[2][0] ? "YES" : "NO");
  }
}

Measured memory_bytes: 13268
#include <bits/stdc++.h>
#define rep(i,N) for (int i = 0; i < (N); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;

bool is_palindrome(string s){
  string t(s.rbegin(), s.rend());
  return s == t;
}

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

  int N = S.size();
  if (is_palindrome(S) && is_palindrome(S.substr(0, (N - 1) / 2)) && is_palindrome(S.substr((N + 1) / 2))){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }

}


Measured memory_bytes: 3584
#include <iostream>
#include <string>
using namespace std;
int main(){
    string s, p;
    cin >> s >> p;
    int size_s = s.size(), size_p = p.size(), count = 0;
    s = s + s; //長さは2*size_s

    for (int i=0; i<((2*size_s)-size_p+1); i++){
        if (p == s.substr(i, size_p)){
            count += 1;
        }
    }if (count >= 1){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;      
}


Measured memory_bytes: 3212
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<int,int>;

ll f(ll a,ll b){
  return a*a*a*a*a + b*b*b*b*b;
}
int main() {
  ll x;
  cin >> x;
  ll a = 0, b = 0;
  while(f(a,0)<x) ++a;
  while (true){
    ll val = f(a,b);
    if(val == x) break;
    if(val>x) --a;
    else ++b;
  }
  cout << a << " " << (-b) << endl;
}

Measured memory_bytes: 3604
#include<iostream>
    #include<stdio.h>
    //#include <bits/stdc++.h>
    #include<vector>
    #include<algorithm>
    #include<string>
    #include<cstring>
    #include<math.h>
    #include<sstream>
    #include<set>
    #include<map>
    #include<queue>

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

    #define INF 10000000
    #define rep(i,n)for(int i=0;(i)<(int)(n);i++)
    #define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
    #define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
    #define vec(type,n) vector<type>(n)
    #define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))

    const int dx[4] = {1,0,-1,0};
    const int dy[4] = {0,1,0,-1};
    
    auto seen = vec(bool,500);
    
    void dfs(Graph &G,int v){
      seen[v] = true;

      for(auto nv : G[v]){
        if(seen[nv] == true)continue;
        dfs(G,nv);
      }

    }
     
    

    
    int main(){
      int n;
      cin>>n;
      
      map<string,int> mp;
      int sum;
      auto s = vec(string,n);
      rep(i,n){
        cin >> s[i];
        cin>>mp[s[i]];
        sum += mp[s[i]];
      }
      string x;
      cin>>x;
      int a;

      rep(i,n){
        sum -= mp[s[i]];
        if(s[i] == x)break;

      }
      cout << sum <<endl;
      }

     
    

    

     

Measured memory_bytes: 256
n,k=gets.chomp.split(" ").map(&:to_i)
ws = []
n.times do
    ws.push(gets.to_i)
end

ret = (ws.max..ws.inject(:+)).bsearch do |e|
    cnt = 1
    truck = 0
    ws.each do |w|
        if truck + w <= e
            truck+=w
        else
            cnt+=1
            truck=w
        end
    end
    cnt <= k
end
puts ret


Measured memory_bytes: 7780
#include<iostream>
#include<set>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
 char S[3],T[3];
 for(int i = 0;i < 3;i++)cin>>S[i];
 for(int i = 0;i < 3;i++)cin>>T[i];
 int g = 0;
 for(int i = 0;i < 3;i++){
     if(S[i] == T[i])g += 1;
 }
 cout<<g;
}

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

int main(){
  string s;
  cin >> s;
  int n = s.size();
  int sum = 0;
  rep(i,n) sum += (int)(s[i]-'0');
  if(sum%9 == 0) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 3720
def please(n , a):

    for i in range(n):
        if a[i] % 2 == 0:
            if a[i] % 3 != 0 and a[i] % 5 != 0:
                return "DENIED"
    
    return "APPROVED"

def main():
    n = int(input())
    a = list(map(int,input().split()))
    print(please(n , a))

if __name__ == '__main__':
    main()

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

using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef long double ld;
typedef vector<ld> vd;
typedef bool bl;
typedef vector<bl> vb;
typedef unordered_map<ll,unordered_map<ll,ll>> graph;

const ll e5 = 1 << 20;
const ll mod = 1000000007;
const ll e3 = 1 << 13;
const ll INF = 1ll << 60;

string s;
string r;
ll t;
ll dp[302][302][302];
ll ans;

int main(){
  cin >> s;
  cin >> t;
  r = s;
  reverse(r.begin(),r.end());
  // cerr << r << endl;
  // cerr << s << endl;
  for(ll i = 0;i < s.size();i++){
    for(ll j = 0;j < s.size();j++){
      for(ll k = 0;k <= t;k++){
        if(s[i] == r[j]){
          dp[i+1][j+1][k] = max(dp[i+1][j+1][k],dp[i][j][k]+1);
        }else{
          dp[i+1][j+1][k+1] = max(dp[i+1][j+1][k+1],dp[i][j][k]+1);
        }
        dp[i+1][j][k] = max(dp[i+1][j][k],dp[i][j][k]);
        dp[i][j+1][k] = max(dp[i][j+1][k],dp[i][j][k]);
      }
    }
  }
  // cerr << s.size() << endl;
  // for(ll k = 0;k <= t;k++){
  //   for(ll i = 0;i <= s.size();i++){
  //     for(ll j = 0;j <= s.size();j++){
  //       cerr << dp[i][j][k] << " ";
  //     }
  //     cerr << endl;
  //   }
  //   cerr << endl;
  //   cerr << endl;
  // }

  for(ll i = 0;i < s.size();i++){
    for(ll k = 0;k <= t;k++){
      ans = max(ans,dp[i][s.size()-i-1][k]*2+1);
    }
  }
  for(ll i = 1;i < s.size();i++){
    for(ll k = 0;k <= t;k++){
      ans = max(ans,dp[i][s.size()-i][k]*2);
    }
  }
  cout << ans << endl;

}


Measured memory_bytes: 215424
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for(int i = (n) - 1; (i) >= 0; --i)
#define SZ(n) (int)(n).size()
#define ALL(n) (n).begin(), (n).end()
#define MOD LL(1e9 + 7)
#define INF 1000000
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PI;

int main() {
	string n;
	cin >> n;
	int t = n[0] - '0';
	int ans = (n.size() - 1) * 9;
	bool f = true;
	FOR(i, 1, n.size()) {
		if (n[i] != '9')
			f = false;
	}
	if (f)
		cout << t + ans << endl;
	else
		cout << t + ans - 1 << endl;
	return 0;
}


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

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a.rbegin(),a.rend());
    int ans=0;
    for(int i=0;i<n;i++){
        ans=i&1?ans-a[i]:ans+a[i];
    }
    cout<<ans<<endl;
}

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

int main() {
  int n;
  cin >> n;
  vector< vector<int> > abc(n, vector<int>(3));
  for (int i = 0; i < n; ++i) cin >> abc[i][0] >> abc[i][1] >> abc[i][2];

  vector< vector<int> > dp(n + 1, vector<int>(3, 0));
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < 3; ++j) {
      for (int k = 0; k < 3; ++k) {
	if (j == k) continue;
	dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + abc[i][j]);
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < 3; ++i) ans = max(ans, dp[n][i]);
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 14080
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			scanner.nextInt();
			String s = scanner.next();
			int count = 0;
			int start = 0, index;
			while ((index = s.indexOf("ABC", start)) >= 0) {
				count++;
				start = index + 1;
			}
			System.out.println(count);
		}
	}
}


Measured memory_bytes: 21716
n = int(input())
n_lst = list(map(int, input().split()))
sorted_lst = sorted(n_lst)
cost = 0

for i in range(n):
    a = n_lst.index(sorted_lst[i])
    j = 0
    while a > i:
        j += 1
        b = n_lst.index(sorted_lst[a])
        cost += n_lst[b]
        n_lst[a],n_lst[b] = n_lst[b],n_lst[a]
        a = b
    cost += min(sorted_lst[i]*j,sorted_lst[i]*2+sorted_lst[0]*(j+2))
print(cost)



Measured memory_bytes: 5624
#include "bits/stdc++.h"
using namespace std;

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

    for(int i=0; i < N; i++){
        int A;
        cin >> A ;

        int count = 0;
        while(A%2==0){
            A/=2;
            count++;
        }

        if(i==0) result = count;
        if(result>count) result = count;
    }

    cout << result << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define chal ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int main()
{
    int k,i,p;
    cin>>k;
    string s;
    cin>>s;
    p=s.size();
    if(p<=k)
        cout<<s<<endl;
    else{
    for(i=0;i<k;i++)
    {
        cout<<s[i];
    }
    cout<<"...";
    }
    return 0;
}


Measured memory_bytes: 3628
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 200000+100;

int n,tmp;
int a[maxn];

int main()
{
	scanf("%d",&n);
	for(int i = 1;i <= n;i++)
	{
		scanf("%d",&tmp);
		a[tmp] = i;
	}
	int ans = 1;
	int k = 1;
	for(int i = 1;i <= n-1;i++)
	{
		k = 1;
		while(a[i] < a[i+1])
		{
			i++;
			k++;
		}
		ans = max(ans,k);
	}
	printf("%d\n",n-ans);
	return 0;
} 

Measured memory_bytes: 1152
N,T=map(int,input().split())
S=list(map(int,input().split()))
t=0
for i in range(0,N-1):
    if S[i+1]-S[i]<T:
        t+=S[i+1]-S[i]
    if S[i+1]-S[i]>=T:
        t+=T
p=t+T
print(p)

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

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long

const int maxN = 200011;

int n, i, p, a, b, c;
ll s[maxN];
int le[maxN], ri[maxN];
ll ans = 1LL << 60;

ll check(ll a, ll b, ll c) {
    ll A = s[a];
    ll B = s[b] - s[a];
    ll C = s[c] - s[b];
    ll D = s[n] - s[c];

    ll M = max(max(A, B), max(C, D));
    ll m = min(min(A, B), min(C, D));

    return M - m;
}

int main()
{
    //freopen("test.in","r",stdin);

    cin >> n;
    for (i = 1; i <= n; i++) {
        cin >> s[i];
        s[i] += s[i - 1];
    }

    p = 0;
    for (i = 1; i <= n; i++) {
        while (p + 1 <= i && s[i] - s[p + 1] >= s[p]) p++;
        le[i] = p;
    }

    p = n + 1;
    for (i = n; i >= 1; i--) {
        while (p - 1 >= i && s[p - 1] - s[i - 1] >= s[n] - s[p - 1]) p--;
        ri[i] = p;
    }

    for (i = 2; i + 2 <= n; i++) {
        b = i;
        for (a = le[i]; a <= le[i] + 1 && a < b; a++) {
            for (c = max(b + 1, ri[i + 1] - 1); c <= ri[i + 1]; c++) {
                ans = min(ans, check(a, b, c));
            }
        }
    }

    cout << ans;


    return 0;
}


Measured memory_bytes: 3328
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
typedef long long ll;
typedef long double ld;
int main(){
    int n,q,l,r,count;
    string s;
    cin>>n>>q>>s;
    vector<int> v(n);
    REP(i,n-1){
        if(s[i]=='A' && s[i+1]=='C'){
            count++;
        }
        v[i+1]=count;
    }
    REP(i,q){
        cin>>l>>r;
        int num=v[r-1]-v[l-1];
        cout<<num<<endl;
    }
    return 0;
}


Measured memory_bytes: 3828
#include "bits/stdc++.h"
using namespace std;

int main(int argc, char const* argv[])
{
  int n, y;
  cin >> n >> y;

  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= n-i; j++) {
        if(1000 * i + 5000 * j + 10000 * (n-i-j) == y)
        {
          cout << n-i-j <<' '<< j <<' '<< i << endl;
          return 0;
        }
    }
  }
  cout << "-1 -1 -1" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(void){
    register long i;
    long n;
    scanf("%ld",&n);
    long a[n];
    for(i = 0;i < n;i++)scanf("%ld",&a[i]);
    long long ans = 0;
    long befmax = a[0];
    for(i = 0;i < n;i++){
        if(a[i] < befmax)ans += befmax - a[i];
        else befmax = a[i];
    }
    printf("%lld",ans);
}

Measured memory_bytes: 3296
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
#define rep(i, n) for(ll i = 0;i < n;i++)
#define all(i) i.begin(), i.end()
template<class T, class U> bool cmax(T& a, U b) { if (a<b) {a = b; return true;} else return false; }
template<class T, class U> bool cmin(T& a, U b) { if (a>b) {a = b; return true;} else return false; }

ll n;

void dfs(ll i, ll cnt, string s) {
  rep(j, cnt) {
    char c = (char)('a'+j);
    if (i != n) dfs(i+1, cnt + (j == cnt-1) , s+c);
    else cout << s << c << endl;
  }
}

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

  cin >> n;
  dfs(1, 1, "");
}


Measured memory_bytes: 1536
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<deque>
#include<cmath>
#include<map>
#include<unordered_map>
#include<set>
#include<cstring>
#include<iomanip> //cout << fixed << setprecision(15) << x << endl;

using namespace std;
typedef long long ll;
const ll INF = 1e9 + 6;
const ll MOD = 1e9 + 7;
const ll LLINF = 1e18;
#define Pint pair<int, int>
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rnr(i,a,b) for(int i=int(a);i>=int(b);i--)
#define rep(i,b) rng(i,0,b)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
/* -- template -- */

bool isZero(double x) {
    return abs(x) < 0.0001;
}

int main() {
    double X; cin >> X;
    X = (M_PI * X) / 180.0;
    double x = 0.0, y = 1.0;
    double i = 1.0;
    while(!isZero(x) || !isZero(y)) {
        x = x + sin(i * X);
        y = y + cos(i * X);
        i += 1.0;
    }
    cout << i << endl;
}


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

int main()
{
    int a, b;
    cin >> a >> b;
    if (a >= 1 && a <= 9 && b >= 1 && b <= 9)
    {
        cout << a * b << endl;
    }
    else
        cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 3604
ll = [1, 9, 7, 4]

a, b, c, d = map(int, input().split())

if ( a in ll ):
  ll.remove(a)
  if ( b in ll ):
    ll.remove(b)
    if ( c in ll ):
      ll.remove(c)
      if ( d in ll ):
        print("YES")
      else:
        print("NO")
    else:
      print("NO")
  else:
    print("NO")
else:
  print("NO")





Measured memory_bytes: 3060
#include <iostream>
using namespace std;
int main(){
	int n,x;
	cin >> n >> x;
	int i=1,cnt = 1,val;
	cin >> val;
	while(i < n && val <= x){
		++cnt;++i;
		int v;
		cin >> v;
		val += v;
	}
	if(i >= n && val <= x){++cnt;}
	while(i < n){int v;cin >> v;++i;}
	cout << cnt << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){

  int n;
  string str,s1,s2,s1_r,s2_r;

  cin >>n;

  for(int i=0 ; i < n ; i++){
    cin >>str;
    
    set<string> s;
 
    for(int j=1 ; j < str.size() ; j++){
      s1=str.substr(0,j);
      s2=str.substr(j);
      
     
      s.insert(s1+s2);
      
      s1_r=s1;
      
      reverse(s1_r.begin(),s1_r.end());

      s2_r=s2;

      reverse(s2_r.begin(),s2_r.end());

      s.insert(s1_r+s2);
      s.insert(s1+s2_r);
      s.insert(s1_r+s2_r);
      s.insert(s2+s1);
      s.insert(s2_r+s1);
      s.insert(s2+s1_r);
      s.insert(s2_r+s1_r);

    }
   
    cout <<s.size()<<endl;

  }


  return 0;
}

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

int main(){
    int q;
    cin >> q;
    map<string, int> mp;
    for(int i=0; i<q; i++){
        int a;
        string key;
        cin >> a >> key;
        if(a == 0){
            int x;
            cin >> x;
            mp[key] = x;
        }else if(a == 1){
            auto itr = mp.find(key);
            if( itr != mp.end() ) {
                cout << mp[key] << endl;
            } else {
                cout << 0 << endl;
            }
        }else{
            mp.erase(key);
        }
    }
    return 0;
}


Measured memory_bytes: 27672
/**
  * @brief atcoder
  * @author yao
  */
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <utility>
#include <algorithm>
#include <functional>
#include <climits>
#define ft first
#define sd second
#ifdef DBG
#   define dbg_pri(x...) fprintf(stderr,x)
#else
#   define dbg_pri(x...) 0
#   define NDEBUG
#endif //DBG
#include <cassert>

typedef unsigned int uint;
typedef long long int lli;
typedef unsigned long long int ulli;

#define N 524288
#define P 200003

constexpr ulli PRIME = 0xffff00001;
constexpr ulli ntt_add(ulli a, ulli b)
{
    return a+b < PRIME ? a+b : a+b-PRIME;
}
constexpr ulli ntt_sub(ulli a, ulli b)
{
    return b <= a ? a-b : a-b+PRIME;
}
constexpr ulli ntt_mul(ulli a, ulli b)
{
    constexpr ulli len = 64-__builtin_clzll(PRIME);
    constexpr ulli magic = (1ull<<len) % PRIME;
    static_assert(len+(64-__builtin_clzll(magic)) <= 64);
    unsigned __int128 k = (unsigned __int128)a*b;
    ulli hi = k>>len, lo = k&(1ull<<len)-1;
    ulli res = (hi*magic+lo) % PRIME;
    return res;
}
constexpr ulli ntt_pow(ulli a, ulli b)
{
    ulli r = 1;
    while(b)
    {
        if(b&1) r = ntt_mul(r,a);
        a = ntt_mul(a,a);
        b >>= 1;
    }
    return r;
}
constexpr ulli ntt_find()
{
    ulli res = 2;
    while(ntt_pow(res,PRIME/2) != PRIME-1) ++res;
    return res;
}
constexpr ulli OMEGA = (ntt_pow(ntt_find(),PRIME/N));
static_assert(__builtin_popcount(N) == 1);
static_assert(PRIME%N == 1);
static_assert(ntt_pow(OMEGA,N/2) == PRIME-1);
uint ricr(uint k)
{
    k ^= (N-1);
    k ^= -1u >> 1 >> __builtin_clz(k);
    return k;
}
void ntt(ulli *a, ulli ow=OMEGA)
{
    for(int i=0,ii=0;i<N;++i,ii=ricr(ii))
        if(i<ii) std::swap(a[i],a[ii]);
    for(int n2=1,n=2;n2<N;n2=n,n*=2)
    {
        ulli w = ntt_pow(ow,N/n);
        for(ulli *p=a; p!=a+N; p+=n)
        {
            ulli k = 1;
            for(int i=0,j=n2;i<n2;++i,++j)
            {
                ulli e = p[i], o = p[j];
                ulli ok = ntt_mul(o,k);
                p[i] = ntt_add(e,ok);
                p[j] = ntt_sub(e,ok);
                k = ntt_mul(k,w);
            }
        }
    }
}
void ntt_inv(ulli *a)
{
    ntt(a,ntt_pow(OMEGA,PRIME-2));
    for(int i=0;i<N;++i) a[i] = ntt_mul(a[i],ntt_pow(N,PRIME-2));
}

int po[N], lo[N];
ulli a[N];

int main()
{
    for(int i=0, k=1; i<P-1; ++i, k=k*2%P)
        po[i] = k, lo[k] = i;
    int n;
    lli ans = 0;
    scanf("%d", &n);
    for(int i=0;i<n;++i)
    {
        int k;
        scanf("%d", &k);
        if(!k) continue;
        ++a[lo[k]];
        ans -= (lli)k*k % P;
    }
    ntt(a);
    for(int i=0;i<N;++i) a[i] = ntt_mul(a[i],a[i]);
    ntt_inv(a);
    for(int i=0;i<N;++i)if(a[i])
        ans += po[i%(P-1)] * a[i];
    assert(ans%2==0);
    ans /= 2;
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 7356
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e6 + 5;
const ll INF = 1LL << 60;
ll bar[maxn];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    ll tmp;
    for (int i = 1; i <= n; ++i) {
        cin >> tmp;
        bar[i] = bar[i - 1] + tmp;
    }
    ll ans = INF;
    for (int i = 1; i <= n - 1; ++i)
        ans = min(ans, abs((bar[n] - bar[i]) - bar[i]));
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 1792
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> P;
#define INF 10000000000000
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for(ll i = 1; i < (ll)(n); i++)
#define repN_1(i, n) for(ll i = 0; i < (ll)(n - 1); i++)
#define repM(i, n) for(ll i = (ll)(n - 1); i >= 0; i--)
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }

int main()
{
	cout << fixed << setprecision(18);

	string s;

	cin >> s;

	if (s == "ABC")
		cout << "ARC" << endl;
	else if (s == "ARC")
		cout << "ABC" << endl;

	return 0;
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
constexpr int MOD = 1000000007;
constexpr int INF = 2147483647;
void yes(bool expr) {
  cout << (expr ? "Yes" : "No") << "\n";
}
struct Node;
vector<Node> V;
struct Node {
  int H;
  vector<int> nbr;
  bool vst = false;
};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N, M;
    cin >> N >> M;
    REP(i, N) {
        V.emplace_back();
        int H;
        cin >> H;
        V[i].H = H;
    }
    REP(i, M) {
        int A, B;
        cin >> A >> B;
        A--;
        B--;
        V[A].nbr.push_back(B);
        V[B].nbr.push_back(A);
    }
    int ans = 0;
    REP(i, N) {
        bool flg = true;
        for(int x : V[i].nbr) {
            if(V[x].H >= V[i].H) {
                flg = false;
                break;
            }
        }
        if(flg) ans++;
    }
    cout << ans << endl;
}

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

#define rep(i,n) for (ll i = 0; i < (n); ++i)
#define All(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()   //reverse
#define strall(v) (v).cbegin(),(v).cend() //const_itterator
#define IN(a, b, x) (a<=x&&x<b)
using namespace std;
using ll = long long;
using Pair = pair<int,int>;
using Graph = vector<vector<ll>>;
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<typename t, typename u, typename Comp=less<>>
bool chmax(t& xmax, const u& x, Comp comp={}) { if(comp(xmax, x)) { xmax = x; return true; } return false;}
template<typename t, typename u, typename Comp=less<>>
bool chmin(t& xmin, const u& x, Comp comp={}) { if(comp(x, xmin)) { xmin = x; return true;} return false;}
const int INF = 1e9;
const ll infl = ll(1e18)+5;

/*
*ios::sync_with_stdio(false);
*cin.tie(0);
*/
//UnionFind

int main(){
  int N;cin >> N;
  vector<int> A(N);
  rep(i,N) cin >> A[i];
  map<int,ll> mp;
  rep(i,N){
    mp[A[i]]++;
    mp[A[i]-1]++;
    mp[A[i]+1]++;
  }
  ll ans = 0;
  for(auto m:mp){
    ans = max(m.second,ans);
  }
  cout << ans << endl;

}

Measured memory_bytes: 6528
#include<iostream>
#include<algorithm>
#include<set>
#include<math.h>
#include<vector>
#include<sstream>
#include<queue>
#include<functional>
#include<bitset>
#include<cstdio>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include <string.h>

using ll = long long;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, x) for(int i=1;i<=(int)(x);i++)
#define rrep(i, x) for(int i=((int)(x)-1);i>=0;i--)
#define rreps(i, x) for(int i=(int)(x);i>0;i--)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define vll vector<ll>
#define vi vector<int>
#define vpll vector<pair<ll,ll>>
#define vpi vector<pair<int,int>>
#define mod 1000000007
#define put2darr(arr, row, col) rep(i, row) { rep(j, col) { printf("%18d", arr[i][j]); } cout << endl; }
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;
}

/* 1..10
 * rep:   0 1 2 3 4 5 6 7 8 9
 * reps:  1 2 3 4 5 6 7 8 9 10
 * rrep:  9 8 7 6 5 4 3 2 1 0
 * rreps: 10 9 8 7 6 5 4 3 2 1
 */
using namespace std;
using Edge = pair<int,int>;
using Graph = vector<vector<Edge> >;

// 入力
int N;
Graph G;

// res は答え
vector<int> res;

// v を c に塗る。p は v の親
void dfs(int v, int p, int c) {
    res[v] = c;
    for (auto e : G[v]) {
        if (e.first == p) continue;
        if (e.second & 1) dfs(e.first, v, 1-c);
        else dfs(e.first, v, c);
    }
}

int main() {
    cin >> N;
    G.assign(N, vector<Edge>());
    for (int i = 0; i < N-1; ++i) {
        int u, v, w; cin >> u >> v >> w;
        --u, --v;
        G[u].push_back(Edge(v, w));
        G[v].push_back(Edge(u, w));
    }
    res.assign(N, 0);
    dfs(0, -1, 1);
    for (auto v : res) cout << v << endl;
}



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

const long long INF = 1LL << 60;

int main() {
    int N; cin >> N;
    long long h[100010];
    for(int i = 0; i < N; i++) {
       cin >> h[i];
    }
    long long dp[100010];
    for(int i = 0; i < N+10; i++) {
        dp[i] = INF;
    }
    dp[0]=0;
    for(int i = 1; i < N; i++) {
        dp[i] = min(dp[i], dp[i-1]+abs(h[i]-h[i-1]));
        if(i> 1) dp[i]=min(dp[i], dp[i-2]+abs(h[i]-h[i-2]));
    }
    cout << dp[N-1] << endl;
}

Measured memory_bytes: 1792
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define SORT(a) sort(a.begin(), a.end())
#define RSORT(a) sort(a.rbegin(), a.rend())
#define REP(i, n) for (int i = 0; i < n; i++)
#define RREP(i, n) for (int i = n; 0 <= i; i--)
#define FOR(i, start, end) for (int i = start; i < end; i++)
#define FORSTEP(i, start, end, step) for (int i = start; i < end; i += step)
#define RFOR(i, start, end) for (int i = start; end <= i; i--)
#define ALL(a) a.begin(), a.end()
#define MOD(a) a %= 1000000007
typedef long long ll;
const int INF32 = 2147483647;
const ll INF64  = 9223372036854775807;
using namespace std;

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

    int N;
    cin >> N;
    vector<int> A(N);
    REP(i, N) cin >> A[i];
    ll ans = 0;

    int a = 0;

    REP(i, N) {
        if (A[i] < 0)
            a++;
    }

    if (a % 2 == 0) {
        REP(i, N) ans += abs(A[i]);
    } else {
        REP(i, N) A[i] = abs(A[i]);
        SORT(A);
        FOR(i, 1, N) ans += A[i];
        ans -= A[0];
    }
    cout << ans << endl;

    return 0;
}

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

double dist(int x1, int y1, int x2, int y2) {
  double a = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
  a = sqrt(a);
  return a;
}

int main() {
  int n;
  cin >> n;
  vector<int> x(n), y(n);
  rep(i, n) { cin >> x[i] >> y[i]; }

  double sum = 0.0;
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      sum += dist(x[i], y[i], x[j], y[j]);
    }
  }
  double ans = sum / n * 2;
  cout << setprecision(15) << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
using namespace std;
static const int MAX_N = 300;

int N;
string S[MAX_N];

int main(){
	cin >> N;
	for(int i = 0; i < N; i++){
		cin >> S[i];
		S[i] += S[i];
	}
	int ans = 0;
	for(int i = 0; i < N; i++){
		bool flag = true;
		for(int j = 0; j < N; j++){
			for(int k = 0; k < N; k++){
				if(S[j][i + k] != S[k][i + j]) flag = false;
			}
		}
		if(flag) ans += N;
	}
	cout << ans << endl;
	return 0;
}

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

#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, m, n) for(int i = (int)(m); i < (int)(n); ++i)

const int MOD = 1e+9 + 7;


template <typename T>
T pow_mod(T n, T p, T m)  // (n^p) % m
{
    if(p == 0) return 1;
    if(p%2 == 1) return pow_mod<T>(n, p-1, m) * n % m;
    else{
        T tmp = pow_mod<T>(n, p/2, m) % m;
        return tmp * tmp % m;
    }
}

// nCk を O(n) で求めるクラス
template <typename T>
class Combination 
{
    private:
        T _mod;
        std::vector<T> factorial, factorial_inv;

    public:
        Combination(int n, int mod): _mod(mod), factorial(n+1, 1), factorial_inv(n+1)
        {
            for(int i = 1; i <= n; ++i) factorial[i] = (i*factorial[i-1]) % _mod;
            factorial_inv[n] = pow_mod<T>(factorial[n], _mod-2, _mod);  // 逆元を取る操作は重いので一回のみ行う
            for(int i = n; i >= 1; --i) factorial_inv[i-1] = (i*factorial_inv[i]) % _mod;
        } 

        T operator()(int n, int k)
        {
            if(n < 0 or k > n) return 0;
            return factorial[n] * factorial_inv[k] %_mod * factorial_inv[n-k] %_mod;
        }
};


int main()
{
    long long n, k;
    cin >> n >> k;

    Combination<long long> comb(n, MOD);
    
    long long ans = 0;
    FOR(i, 0, min(n, k+1)){
        ans += (comb(n,i)*comb(n-1, n-i-1)) % MOD;
        ans %= MOD;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3328
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {
  int e;
  while (cin >> e && e != 0) {
    int m = e;
    for (int z=0; z*z*z <= e; z++) {
      int y = (int)sqrt(e - z*z*z);
      int x = e - (y*y + z*z*z);
      m = min(m, x+y+z);
    }
    cout << m << endl;
  }
  return 0;
}

Measured memory_bytes: 3000
#include<stdio.h>
#include<math.h> 
#include<string.h>
int main(){
	int n,a[100007];
	scanf("%d",&n);
	for(int j = 1;j<=n;j++){
		scanf("%d",&a[j]);
	}
	int i = 1,sum = 0;
	while(i!=2){
		i = a[i];
		sum++;
		if(sum>100000) break;
	}
	if(i==2) printf("%d\n",sum);
	else printf("-1\n");
}

Measured memory_bytes: 512
#include <stdio.h>

int main(void){
  int N,M,X,Y;
  scanf("%d%d%d%d",&N,&M,&X,&Y);
  int x,y;
  int max = -101;
  int min = 101;

  for(int i = 0;i < N;i++){
    scanf("%d",&x);
    if(max < x){
      max = x;
    }
  }
  for(int i = 0;i < M;i++){
    scanf("%d",&y);
    if(min > y){
      min = y;
    }
  }

  for(int Z = min;Z > max;Z--){
    if(X == Z || Y == Z) continue;
    if(max < min && Z > max && X < Z && Z <= Y){
      printf("No War\n");
      return 0;
    }
  }

  printf("War\n");
  return 0;
}

Measured memory_bytes: 128
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/* 
 * File:   main.c
 * Author: kundaikwangwari
 *
 * Created on August 1, 2019, 8:38 AM
 */

#include <stdio.h>
#include <stdlib.h>
#define Free -1
#define Not_Free -2
#define Queens 8
#define Valid 1
/*
 * 
 */

int Col[Queens], Board[Queens][Queens],Row[Queens],drop[Queens*2 - 1],dneg[Queens*2 - 1];

void DisplayAns(){
    
    for(int i = 0; i < Queens; i++){
        for(int j = 0; j < Queens; j++){
            if(Board[i][j] == Valid){
                if(Row[i] != j)return;
            }
        }
    }
    
    for(int i = 0; i < Queens; i++){
        for(int j = 0; j < Queens; j++){
            if(Row[i] == j)printf("Q");
            else printf(".");
        }
        printf("\n");
    }
return;
}

void PutQueen(int pos){
    
    if(pos == Queens){
        DisplayAns();
        return;
    }
    
    for(int j = 0; j < Queens; j++){
        if((Col[j] == Not_Free) || (drop[pos + j] == Not_Free)
                || (dneg[pos - j + Queens - 1] == Not_Free))continue;
        
        Row[pos] = j;
        Col[j] = drop[pos + j] = dneg[ pos - j + Queens - 1] = Not_Free;
        
        PutQueen(pos + 1);
        
        Row[pos] = Col[j] = drop[pos + j] = dneg[pos - 1 + Queens - j] = Free;
        
    }
}


int main(int argc, char** argv) {

    
    for(int i = 0; i < Queens; i++){
        for(int j = 0; j < Queens; j++)Board[i][j] = 0;
    }
    
    for(int i = 0; i < Queens; i++){
        Col[i] = Free;
        Row[i] = Free;
    }
    
    for(int i = 0; i < Queens*2 - 1; i++){
        drop[i] = Free;
        dneg[i] = Free;
    }
    int n;
    scanf("%d",&n);
    int x[n], y[n];
    for(int i = 0; i < n; i++){
        scanf("%d %d",&x[i],&y[i]);
        //printf("%d %d\n",x[i],y[i]);
        Board[x[i]][y[i]] = Valid;
        //printf("board[%d][%d] is %d\n",x[i],y[i],Board[x[i]][y[i]]);
    }
    
    PutQueen(0);
    return (0);
}




Measured memory_bytes: 2112
local function meld(a,b)
    if not a then
        return b
    elseif not b then
        return a
    elseif a[1]<b[1] then
        b[4]=a[3]
        a[3]=b
        return a
    else
        a[4]=b[3]
        b[3]=a
        return b
    end
end

local function pair(a,d)
    local b=a and a[4]
    if b then
        local c=b[4]
        a=meld(a,b)
        a[4]=d
        d=a
        return pair(c,d)
    else
        local e
        while d do
            e=d
            d=d[4]
            a=meld(a,e)
        end
        return a
    end
end

local PairingHeap={}

PairingHeap.empty=function(self)
    return not self[1]
end

PairingHeap.push=function(self,key,value)
    self[1]=meld(self[1],{key,value,false,false})
end

PairingHeap.top=function(self)
    return self[1][2]
end

PairingHeap.pop=function(self)
    self[1]=pair(self[1][3],false)
end

PairingHeap.join=function(self,other)
    self[1]=meld(self[1],other[1])
    return self
end

PairingHeap.new=function(self)
    local obj={false}
    setmetatable(obj,{__index=PairingHeap})
    return obj
end

----------

local n,m=io.read("n","n")
local a=PairingHeap:new()
for i=1,n do
    local input=io.read("n")
    a:push(-input,input)
end
 
for i=1,m do
    local x=a:top()
    x=math.floor(x/2)
    a:pop()
    a:push(-x,x)
end
 
local total=0
for i=1,n do
    total=total+a:top()
    a:pop()
end
print(string.format("%d",total))

Measured memory_bytes: 18072
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <string>
#include <tuple>
#include <functional>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <map>
//#include "toollib.h"
#pragma warning (disable:4018)
#define INT_MAX 2147483647

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	vector<int> b{ a[0] };
	for (int i = 0; i < n; i++) {
		if (a[i] > b.back()) b.push_back(a[i]);
		else {
			for (int j = 0; j < b.size(); j++) {
				if (b[j] >= a[i]) {
					b[j] = a[i];
					break;
				}
			}
		}
	}
	cout << b.size() << endl;
	return 0;
}

Measured memory_bytes: 3900
#include <stdio.h>

int main(void){

    int num,i,line[1000];
    double sum,sum1;

    for(;sum=0.0,sum1=0.0,scanf("%d",&num),num;){
        for(i=0;i<num;sum+=line[i],i++)
            scanf("%d",&line[i]);
        sum/=num;
        for(i=0;i<num;i++)
            sum1+=pow((line[i]-sum),2);
        sum1/=num;

        printf("%f\n",sqrt(sum1));

    }
    return 0;
}

Measured memory_bytes: 636