akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoders {
	class Program {
		static void Main(string[] args) {
			var inputArray = retreiveLongArray();
			var inputCount = 1;

			// 不正な入力は処理しない
			if (inputArray.Length != inputCount) {
				Console.WriteLine("invalid input");
				return;
			}
			var N = inputArray[0];

			var dictionary = new Dictionary<string, long>();

			for (int i = 1; i <= N; i++) {

				var initial = getInitial(i);
				var end = i % 10;
				var pair = initial + "_" + end;

				//Console.WriteLine($"({initial},{end})");

				if (dictionary.ContainsKey(pair)) {
					dictionary[pair] += 1;
				}
				else {
					dictionary.Add(pair, 1);
				}

			}

			long count = 0;
			for (int i = 1; i <= N; i++) {

				var initial = getInitial(i);
				var end = i % 10;

				var targetPair = end + "_" + initial;

				if (!dictionary.ContainsKey(targetPair)) {
					continue;
				}

				count += dictionary[targetPair];

			}


			//答えの出力
			var ans = count;
			Console.WriteLine(ans);

		}

		/// <summary>
		/// スペースで区切られた文字列配列の入力を受け取る
		/// </summary>
		/// <returns></returns>
		private static string[] retreiveStringArray() {
			var inputArray = Console.ReadLine().Split(' ');
			return inputArray;
		}

		/// <summary>
		/// ある整数の先頭の桁を取得する
		/// </summary>
		/// <returns></returns>
		private static int getInitial(long n) {

			while (n >= 10) {
				n = n / 10;
			}
			return (int)n;
		}

		/// <summary>
		/// スペースで区切られた整数配列の入力を受け取る
		/// </summary>
		/// <returns></returns>
		private static long[] retreiveLongArray() {
			var inputArray = Console.ReadLine().Split(' ');
			var longArray = inputArray.Select(s => long.Parse(s));
			return longArray.ToArray();
		}
	}
}

Measured memory_bytes: 15524
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
typedef long long LL;
int N;
typedef pair<int,int>P;
vector<int>G[1001];
int X[1001];
bool check=true;

int dp[1011][5011];

int dfs(int x){
    vector<P>v;
    LL ans=0;
    REP(i,G[x].size()){
        int nxt=G[x][i];
        int a=dfs(nxt);
        v.push_back(P(a,X[nxt]));
        ans+=a;
        ans+=X[nxt];
    }
    REP(i,G[x].size()+1){
        REP(j,5001){
            dp[i][j]=-1;
        }
    }
    dp[0][0]=0;
    REP(i,G[x].size()){
        REP(j,5001){
            if(dp[i][j]==-1)continue;
            if(j+v[i].first<5001){
               dp[i+1][j+v[i].first]=0;
            }
            if(j+v[i].second<5001){
               dp[i+1][j+v[i].second]=0;
            }
        }
    }
    LL res=-1;
    REP(i,5001){
        if(dp[G[x].size()][i]==0&&i<=X[x]){
           res=i;
        }
    }
    if(res==-1){
       check=false;
       return -1;
    }
    //cout<<ans<<" "<<res<<endl;
    return ans-res;
}


int main(){
    cin>>N;
    REP(i,N-1){
        int a;
        cin>>a;
        a--;
        G[a].push_back(i+1);
    }
    REP(i,N){
        cin>>X[i];
    }
    dfs(0);
    if(check){
       cout<<"POSSIBLE"<<endl;
    }else{
       cout<<"IMPOSSIBLE"<<endl;
    }
    return(0);
}

Measured memory_bytes: 19840
using System;
using System.Collections.Generic;
using System.Linq;
public class Hello{
    public static void Main(){
        var s = Console.ReadLine();
        var n = s.Length;
        long ans = 0;
        for(var i = 0;i < Math.Pow(2,n - 1);i++){
            var temp = "";
            for(var j = 0;j < n - 1;j++){
                temp += s.Substring(j,1);
                if((1 & i >> j) == 1){
                    temp += "+";
                }
            }
            temp += s.Substring(n - 1,1);
            ans += Calc(temp);
        }
        Console.WriteLine(ans);
    }
    static long Calc(string s){
        var list = s.Split('+').Select(long.Parse).ToList();
        return list.Sum();
    }
}


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

using namespace std;

int main() {
#if DEBUG
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cout.precision(10);
    cout << fixed;
    int n; cin >> n;
    double under = 0.0;
    for (int i = 0; i < n; ++i) {
        int num; cin >> num;
        under += 1.0 / num;
    }
    cout << 1.0 / under << '\n';
}



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

template<typename T>
struct segment_tree {
    long long N; // 木の頂点数
    long long M; // 葉の数
    std::vector<T> V; // セグメント木　1-indexed
    std::function<T(T, T)> op; // 二項演算
    T id; // 単位元
    
    // ===============================================================
    
    segment_tree(std::vector<T>& a, std::function<T(T, T)> op, T id) : op(op), id(id) {
        M = 1;
        while (M < a.size()) M *= 2;
        N = 2 * M;
        V.resize(N, id);
        for (long long i = 0; i < a.size(); i++) V[M + i] = a[i];
        for (long long i = a.size(); i < M; i++) V[M + i] = id;
        for (long long i = M - 1; i > 0; i--) {
            V[i] = op(V[2 * i], V[2 * i + 1]);
        }
    }
    
    // ===============================================================
    
    void point_update(long long i, T x) {
        i += M;
        V[i] = x;
        while (i / 2 < i) {
            i /= 2;
            V[i] = op(V[2 * i], V[2 * i + 1]);
        }
    }
    
    T range_subfunc(long long cur_node, long long cur_left, long long cur_right, long long l, long long r) {
        if (cur_right <= l || r <= cur_left) return id;
        if (l <= cur_left && cur_right <= r) return V[cur_node];
        long long mid = (cur_left + cur_right) / 2;
        return op(range_subfunc(cur_node * 2, cur_left, mid, l, r), range_subfunc(cur_node * 2 + 1, mid, cur_right, l, r));
    }
    
    T range(long long l, long long r) {
        return range_subfunc(1, 0, M, l, r);
    }
};

int main() {
    long long n, q;
    std::cin >> n >> q;
    std::vector<long long> a(n, 0);
    auto f = [] (long long x, long long y) {return x + y;};
    segment_tree<long long> sg(a, f, 0);
    
    while (q--) {
        long long com, x, y;
        std::cin >> com >> x >> y;
        if (com == 0) {
            sg.point_update(x - 1, a[x - 1] + y);
            a[x - 1] += y;
        }
        else std::cout << sg.range(x - 1, y) << std::endl;
    }
}


Measured memory_bytes: 5724
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T> >;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define repb(i, n) for(ll i = (n)-1; i >= 0; i--)
#define repr(i, a, b) for(ll i = (a); i < (b); i++)
#define reprb(i, a, b) for(ll i = (b)-1; i >= (a); i--)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((ll)(x).size())
const ll MOD = 1000000007;
const ll INF = 100000000000000000LL;
inline ll GCD(ll a, ll b){ return b?GCD(b, a % b):a; }
inline ll LCM(ll a, ll b){ return a/GCD(a, b)*b; }
inline ll powint(unsigned long long x, ll y){ ll r=1; while(y){ if(y&1) r*=x; x*=x; y>>=1; } return r; }
inline ll powmod(ll x, ll y, ll m = MOD){ ll r=1; while(y){ if(y&1) r*=x; x*=x; r%=m; x%=m; y>>=1; } return r; }
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; }
#ifdef OJ_LOCAL
#include "dump.hpp"
#else
#define dump(...) ((void)0)
#endif

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    ll n;
    cin >> n;
    vll a(n);
    rep(i, n){
        cin >> a[i];
    }
    /*
    vvi cnt(n, vi(20, 0));
    rep(i, n){
        rep(j, 20){
            cnt[i][j] = (a[i] >> j);
        }
    }
     */
    ll ans = 0;
    ll tmpx = 0;
    ll tmps = 0;
    ll j = 0;
    rep(i, n){
        tmpx ^= a[i];
        tmps += a[i];
        dump(i, j);
        while(tmpx != tmps){
            tmpx ^= a[j];
            tmps -= a[j];
            j++;
            dump(i, j);
        }
        ans += i-j+1;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1792
#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(){
  ll a,b,x;
  cin >> a >> b >> x;
  
  if(a==0) cout << b/x+1;
  else cout << b/x-(a-1)/x;
  
  return 0;
}

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

#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ALL(x) (x).begin(), (x).end()

using namespace std;
typedef long long ll;

int main()
{
    int n;
    cin >> n;
    map<int, ll> cal; vector <int> numeros(n);
    ll suma = 0;
    for ( int i = 0; i < n; ++i )
    {
        cin >> numeros[i];
        cal[numeros[i]] += 1;
    }

    for ( auto i = cal.begin(); i != cal.end(); ++i )
    {
        suma += ( i->second * i->second - i->second ) / 2;
    }

    for ( int i = 0; i < n; ++i )
    {
        cout << ( suma - ( cal[numeros[i]] - 1 ) ) << '\n';
    }

    return 0;
}


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

public class Solution
{
    public static void Main()
    {
        var vals = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        var H = vals[0];
        var W = vals[1];
        var K = vals[2];
        var grid = new string[H];
        for (int i = 0; i < H; i++)
        {
            grid[i] = Console.ReadLine();
        }
        var area = Enumerable.Range(0, H).Select(_ => new int[W]).ToArray();
        int count = 1;
        for (int y = 0; y < H; y++)
        {
            for (int x = 0; x < W; x++)
            {
                if (grid[y][x] == '#')
                {
                    for (int xx = x; xx >= 0 && area[y][xx] == 0; xx--)
                    {
                        area[y][xx] = count;
                    }
                    for (x++; x < W && grid[y][x] != '#'; x++)
                    {
                        area[y][x] = count;
                    }
                    x--;
                    count++;
                }
            }
        }
        for (int y = 0; y < H; y++)
        {
            if (area[y][0] != 0)
            {
                for (int yy = y - 1; yy >= 0 && area[yy][0] == 0; yy--)
                {
                    area[yy] = area[y];
                }
                for (int yy = y + 1; yy < H && area[yy][0] == 0; yy++)
                {
                    area[yy] = area[y];
                }
            }
        }

        var result = string.Join(Environment.NewLine, area.Select(row => string.Join(" ", row)));
        Console.WriteLine(result);
    }
}

Measured memory_bytes: 21468
////////////////////////////////////////////////NITISH//////////////////////////////////////////////


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007
#define fast ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define endl '\n'
#define sz(a) (ll)((a).size())
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define repA(i,a,n) for(int i=a;i<=n;i++)
#define repB(i,a,n) for(int i=a;i>=n;i--)
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()

vector<int>ar[100001];
bool visited[100001];
void dfs(int s){
    visited[s]=true;
    for(auto i:ar[s]){
        if(!visited[i])dfs(i);
    }
}
void solve(){
    ll n,k,a,b,c=0,g,m,ma1=0,ma2=0,x,d=0,y,s1=0,s2=0,y2,z2,q;
    cin>>n>>m;
    memset(visited,false,sizeof(visited));
    rep(i,m){
        cin>>a>>b;
        ar[a].push_back(b);
        ar[b].push_back(a);
    } 
    for(int i=1;i<=n;i++){
        if(!visited[i]){dfs(i);c++;}
    }
    cout<<c-1;
}


int main(){
    ll t=1;
    // cin>>t;
    while(t--){
        solve();
    }

return 0;
}




//////////////////////////////////////////////////////END////////////////////////////////////////////////


Measured memory_bytes: 9684
import Control.Monad
import Control.Applicative
import Data.List

data Point = Point {xp :: Double, yp :: Double}
data Rect = Rect {ld :: Point, ru :: Point}

toRect :: [Double] -> Rect
toRect [x1, y1, x2, y2] = Rect (Point x1 y1) (Point x2 y2)

eps :: Double
eps = 0.0000000001

frf :: Rect -> Rect -> Bool
frf ra rb = s1 || s2 || s3 || s4
  where
    s1 = (xp . ld) rb - (xp . ru) ra > eps
    s2 = (xp . ld) ra - (xp . ru) rb > eps
    s3 = (yp . ld) rb - (yp . ru) ra > eps
    s4 = (yp . ld) ra - (yp . ru) rb > eps

main = do
  xs <- input (map read . words) :: IO [[Double]]
  mapM_ putStrLn $ solve xs

solve :: [[Double]] -> [String]
solve = map f
  where
    f [xa1, ya1, xa2, ya2, xb1, yb1, xb2, yb2] = if frf (toRect [xa1, ya1, xa2, ya2]) (toRect [xb1, yb1, xb2, yb2]) then "NO" else "YES"

input :: (String -> a) -> IO [a]
input f = map f . lines <$> getContents 

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

int main()
{
  string s;
  cin >> s;
  int64_t ans(0);
  int64_t a(0);

  for (int i = 0; i < int(s.length()) - 1; i++) {
    if (s[i] == 'A') a++;
    else if (s[i] == 'B' && s[i + 1] == 'C') {
      ans += a;
      i++;
    } else a = 0;
  }
  cout << ans << endl;
}


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

using namespace std;
using ll = long long;

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

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define debug(x) cout << #x << ": " << x << endl;
#define popcnt __builtin_popcount


int main() {
    string s;
    cin >> s;

    int b = 0;
    for (int i = 0; i < sz(s); i++) {
        b |= (1 << (s[i] - 'a'));
    }

    for (int i = 0; i < 26; i++) {
        if(!(b&(1<<i))){
            cout << (char)('a' + i) << endl;
            return 0;
        }
    }
    puts("None");

    return 0;
}

Measured memory_bytes: 512
#include<stdio.h>

void quick(int a[],int left,int right);

int main(){
  int N,X,small_diff=1000000000,flag=1;
  scanf("%d%d",&N,&X);
  int x[N+1],diff[N];
  x[N]=X;
  for (int i = 0; i < N; i++)
  {
    scanf("%d",&x[i]);
  }

  quick(x,0,N);

  for (int i = 0; i < N; i++)
  {
    diff[i]=x[i+1]-x[i];
    if (small_diff>diff[i]){
      small_diff=diff[i];
    }
  }

  int ans = small_diff;
  while (flag)
  {
    if (ans%small_diff==0)
    {
      ans=small_diff;
      for (int j = 0; j < N; j++)
      {
        if (diff[j]%small_diff==0)
        {
          flag=0;
        }else{
          flag=1;
          break;
        }
      }
    }
    small_diff--;
  }
  
  printf("%d",ans);

  return 0;
}

void quick(int a[],int left,int right)
{
    int s,t,i,j;

    if (left<right){
        s=a[left];            
        i=left; j=right+1;      
        while (1){              
            while (a[++i]<s);
            while (a[--j]>s);
            if (i>=j) break;
            t=a[i]; a[i]=a[j]; a[j]=t;
        }
        a[left]=a[j]; a[j]=s;

        quick(a,left,j-1);
        quick(a,j+1,right);
    }
}

Measured memory_bytes: 2504
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;


const int maxn = 2e5 + 10;
int B[maxn],h[maxn],a[maxn];
int n;
void update(int I,int val)
{
	while(I &&  I < maxn)
	{
		B[I]=max(B[I],val);
		I+=I&-I;
	}
}
int query(int I)
{
	int mx=0;
	while( I > 0 )
	{
		mx=max(mx,B[I]);
		I-=I&-I;
	}
	return mx;
}

int32_t main()
{
	IOS
	cin >> n;
	for(int i=0;i<n;i++)
	cin>>h[i];
	for(int i=0;i<n;i++)
	cin>>a[i];
	
	int ans = 0;
	for(int i=0;i<n;i++)
	{
		int mx = query(h[i]);
		update(h[i],mx+a[i]);
		ans=max(ans,mx+a[i]);
	}
	
	cout << ans << endl;
	
	
}


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

int main() {
  int a,b;
  cin >> a;
  cin >> b;

  if ((a * b) %2 == 0) {
    cout << "Even" << endl;
  } else {
    cout << "Odd" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
import java.util.HashSet;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		HashSet<Integer> hs = new HashSet<>();
		hs.add(sc.nextInt());
		hs.add(sc.nextInt());
		hs.add(sc.nextInt());
		System.out.println(hs.size());
	}
}

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

using namespace std;
typedef long long ll;

#define MOD (long long)(1e9+7)
#define INF (1LL<<60)
#define rep(i,n) for(ll i = 0; i < (n); i++)
#define rep1(i,n) for(ll i = 1; i <= (n); i++)

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


// 最大公約数
ll gcd(ll a, ll b)
{
  if(b == 0) return a;
  return gcd(b, a % b);
}

// mod m におけるa の逆元
ll modinv(ll a, ll m) {
  ll b = m, u = 1, v = 0;
  while (b) {
    ll t = a / b;
    a -= t * b; swap(a, b);
    u -= t * v; swap(u, v);
  }
  u %= m;
  if (u < 0) u += m;
  return u;
}

// 素因数分解
vector<pair<ll, ll>> prim;
void pf(ll n)
{
  ll s = sqrt(n);
  ll r = 0;
  for(ll i = 2; i <= s; i++) {
    if((n % i) == 0) {
      r = 0;
      do {
	r++;
	n = n / i;
      } while((n % i) == 0);
      prim.push_back({i, r});
    }
  }
  if(n > s) {
    prim.push_back({n, 1});
  }
}




void solve()
{
  ll N,K;cin >> N >> K;
  vector<ll> a(N); rep(i, N) cin >> a[i];
  ll ans = 0;
  rep(i, N) {
    ans += (a[i]< K-a[i])? a[i]*2 : (K-a[i]) *2;
  }
  cout << ans << endl;
}


int main(void)
{
  // ll t; cin >> t; rep(i, t)
  solve();
}


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

#define F first
#define S second
#define MP make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define lcm(a, b) (a)/__gcd((a),(b))*(b)
#define endl '\n'

using namespace std;

typedef long long LL;
typedef pair<int, int> P;
typedef pair<LL, LL> LP;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1000000007;
static const int SIZE = 200005;

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

vector<int> Div(int n) {
    vector<int> ret;
    for(int i = 1; i * i <= n; ++i) {
        if(n % i == 0) {
            ret.pb(i);

            if(i * i != n) ret.pb(n / i);
        }
    }
    sort(all(ret));
    return ret;
}

int Z_algorithm(string s) {
    int a[SIZE];
    a[0] = s.size();
    int i = 1, j = 0;
    while(i < s.size()) {
        while(i + j < s.size() && s[j] == s[i + j]) {
            ++j;

        }
        a[i] = j;
        if(j == 0) {
            ++i;
            continue;

        }
        int k = 1;
        while(i + k < s.size() && k + a[k] < j) {
            a[i + k] = a[k];
            ++k;

        }
        i += k;
        j -= k;

    }

    int mx = 0;
    for(int i = 0; i < s.size(); ++i) {
        mx = max(mx, min(i, a[i]));

    }
    return mx;
}

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

    int n;
    cin >> n;
    string s;
    cin >> s;

    int res = 0;
    for(int i = 0; i < s.size(); ++i) {
        string t = s.substr(i);
        res = max(res, Z_algorithm(t));

    }
    cout << res << endl;

    return 0;
}



Measured memory_bytes: 256
// AtCoder template
// sabaより胡蝶しのぶさんの方が可愛いのではないか？
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < n; ++i)


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

    ll h,w; cin >> h >> w;
    if(h == 1 || w == 1){
        cout << 1 << endl;
    }else cout << (h*w+1)/2 << endl;
}

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

typedef long long   ll;
typedef long double ld;
using namespace std;
const int mod=1e9+7;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,x,y;
    cin >> n >> x >> y;

    int count[n-1]={};
    for(int i = 1; i <= n-1; i++) {
        for(int j = i+1; j <= n; j++) {
            int a,b,c;
            a=j-i;
            b=abs(x-i)+1+abs(j-y);
            c=abs(y-i)+1+abs(j-x);
            int d=min({a,b,c});
            count[d-1]++;
        }
    }
    for(int i = 0; i < n-1; i++) {
        cout << count[i] << "\n";
    }
    return 0;
}

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

//bool anti(int n,int k){
//    return k <= (n+1)/2;
//
//
//}
//
//template <typename T>
//void add_vector_map(unordered_map<T, vector<T>>& mp, T key, T val){
//    auto itr = mp.find(key);
//    if (itr != mp.end()){
//        vector<T>& vec = (*itr).second;//ここでcopyは怒る？
//        vec.push_back(val);
//    }else{
//        mp[key] = vector<T>{val};
//    }
//
//}
//
//bool path(const unordered_map<int, vector<int>>& mp){
//    vector<int> one_naver = {};
//    vector<int> two_naver = {};
//    for(auto& pair: mp) {
//        int a = pair.first;
//        auto a_navers = pair.second;
//        if (a_navers.size() == 1)
//            one_naver.push_back(a);
//        else if (a_navers.size() == 2)
//            two_naver.push_back(a);
//        else
//            return false;
//    }
//
//    return (one_naver.size() == 2 && two_naver.size() == 2);
//
//
//
//}

unsigned long long hit_pocket(unsigned long long K, unsigned long long A, unsigned long long B){
    if (B <= A+2)
        return K + 1;
    else if (K <= A)
        return K + 1;
    else{//換金に意味あり
        unsigned long long first_kankin = A - 1;
        if ((K - first_kankin) %2 == 0){
            return A + (B - A)*((K - first_kankin)/2);
        }else{
            return A + (B - A)*((K - first_kankin -1)/2) + 1;
        }

    }
}

//    unordered_map<int, vector<int>> mp;
//
//    for(int i = 0; i <3; i++){
//        int a,b;
//        cin >> a >> b;
//        add_vector_map(mp, a,b);
//        add_vector_map(mp, b,a);
//

int main(){

    unsigned long long K,A,B;

    cin >> K >> A >> B;

    unsigned long long ans = hit_pocket(K,A,B);
    cout << ans;
    return 0;

}

Measured memory_bytes: 256
a=[1e4]*51
for i,j in[(2,380),(3,550),(5,850),(10,1520),(12,1870),(15,2244)]:
 a[i]=j
 for k in range(51-i):a[k+i]=min(a[k]+j,a[k+i])
for n in iter(input,'0'):print(a[int(n)//100])


Measured memory_bytes: 5612
#include <iostream>

using namespace std;

int main() {
  uint64_t a, b, c, x, y;
  cin >> a >> b >> c >> x >> y;
  uint64_t res = 10e15;
  res = min(res, a * x + b * y);
  if (x > y) {
    res = min(res, 2 * c * x);
    res = min(res, 2 * c * y + a * (x - y));
  } else {
    res = min(res, 2 * c * y);
    res = min(res, 2 * c * x + b * (y - x));
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 3608
#![allow(clippy::needless_range_loop)]
#![allow(unused_macros)]
#![allow(dead_code)]
#![allow(unused_imports)]

use itertools::iproduct;
use itertools::Itertools;
use proconio::input;
use proconio::marker::*;

fn main() {
    input! {
        n: usize,
        l: [usize; n]
    }

    let mut ans = 0;
    for i in 0..n {
        for j in i..n {
            for k in j..n {
                if l[i] != l[j]
                    && l[j] != l[k]
                    && l[k] != l[i]
                    && l[i] + l[j] > l[k]
                    && l[j] + l[k] > l[i]
                    && l[k] + l[i] > l[j]
                {
                    ans += 1;
                }
            }
        }
    }

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


Measured memory_bytes: 2172
def main():
    N = int(input())
    A = [int(a) for a in input().split()]
    dist = []
    prev = 0
    for i in range(N):
        dist.append(abs(A[i]-prev))
        prev = A[i]
    dist.append(abs(A[N-1]-0))
    plan_tot = sum(dist)
    for i in range(N):
        v = plan_tot - dist[i] - dist[i+1]
        if i == 0:
            v += abs(A[1])
        elif i == N-1:
            v += abs(A[N-2])
        else:
            v += abs(A[i+1]-A[i-1])
        print(v)

if __name__ == '__main__':
    main()

Measured memory_bytes: 14172
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define fr(i,n,x) for(int i=0;i<n;i+=x)
#define pb push_back
int main(){
	int n;
	cin>>n;
	int x;
	int count=0;
	for(int i=1;i<=n;i++)
	{
		cin>>x;
		if(i%2 && x%2)
		count++;
	}
	cout<<count;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
int check[1000010];
int main(void)
{
	int n;
  	cin >> n;
  	int a[n+5];
  	for(int i=0;i<n;i++)
    {
    	cin >> a[i];
    }
  	for(int i=0;i<1000006;i++)
    {
      check[i] = 0;
    }
  	int ts;
  	int pairwise = 1;
  	int setwise = 1;
  	for(int i=0;i<n;i++)
    {
		ts = a[i];
      if(a[i]%2==0)
      {
        if(check[2]!=0)
        {
          pairwise = 0;
        }
        check[2]++;
      	while(ts%2==0)
        {
        	ts = ts/2;
        }
      }
      for(int j=3;j*j<=a[i];j+=2)
      {
        if(ts%j==0)
        {
          if(check[j]!=0)
          {
            pairwise = 0;
          }
          check[j]++;
          while(ts%j==0)
          {
              ts = ts/j;
          }
        }
      }
      if(ts>1)
      {
        if(check[ts]!=0)
        {
          pairwise = 0;
        }
        check[ts]++;
      }
    }
  	if(check[2]==n)
    {
      setwise = 0;
    }
  	for(int i=3;i<=1000006;i++)
    {
    	if(check[i]==n)
        {
          setwise = 0;
        }
    }
  if(pairwise==1)
  {
    
    cout << "pairwise coprime" << endl;
  }
  else
  {
    if(setwise==1)
    {
      cout << "setwise coprime" << endl;
    }
    else
    {
      cout << "not coprime" << endl;
    }
  }
}

Measured memory_bytes: 11376
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
const int MX = 200005;
int n, m, c[MX][2], a, b, qu[MX], t, k = 1, out[MX];
char s[MX];
vector<int> G[MX];
int main(){
	scanf("%d%d\n%s", &n, &m, s);
	rep(i,m){
		scanf("%d%d", &a, &b);
		G[--a].push_back(--b);
		G[b].push_back(a);
		c[a][s[b]-'A']++;
		c[b][s[a]-'A']++;
	}
	a = b = 0;
	rep(i,n) if(!out[i] && !(c[i][0] && c[i][1])){
		out[qu[b++]=i] = 1;
		while(a < b){
			t = qu[a++];
			for(int u: G[t]) if(!out[u] && !--c[u][s[t]-'A']){
				out[qu[b++]=u] = 1;
			}
		}
	}
	rep(i,n) k &= out[i];
	puts(k ? "No" : "Yes");
}

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

#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl

typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
const int inf = 1000000001;
const ll INF = 1e18 * 4;
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846
#define Sp(p) cout<<setprecision(15)<<fixed<<p<<endl;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };

int main() {
	string s;
	cin >> s;
	int n = s.size(), i;
	for (i = 0; i < n - 1; i++) {
		if (s[i] == 'A' && s[i + 1] == 'C') {
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
}

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

#define ed cout << "\n";
#define speed                         \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define ll long long
#define ffor(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(i, n) ffor(i, 0, n)
#define All(obj) (obj).begin(), (obj).end()
#define INF ((ll)1e9 + 7)
#define c(a) cout << a << "\n";
using namespace std;
const int N = 100005;

int main()
{
    speed;
    cout << fixed << setprecision(10);
    /*start*/
    string s;
    cin >> s;
    vector<int> a(s.size());
    int sum = 0;
    rep(i, s.size())
    {
        a[i] = s[i] - '0';
        sum += a[i];
    }
    string b = "";
    if (sum == 7)
        b = "+++";
    else if (sum - a[1] * 2 == 7)
        b = "-++";
    else if (sum - a[2] * 2 == 7)
        b = "+-+";
    else if (sum - a[3] * 2 == 7)
        b = "++-";
    else if (sum - a[1] * 2 - a[2] * 2 == 7)
        b = "--+";
    else if (sum - a[1] * 2 - a[3] * 2 == 7)
        b = "-+-";
    else if (sum - a[2] * 2 - a[3] * 2 == 7)
        b = "+--";
    else if (sum - a[1] * 2 - a[2] * 2 - a[3] * 2 == 7)
        b = "---";

    rep(i, a.size())
    {
        s.push_back(b[i]);
    }
    b = "";
    rep(i, a.size())
    {
        b += s[i];
        b += s[a.size() + i];
    }
    b.pop_back();
    b += "=7";
    c(b);
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
#AGC37 C

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop,heapify
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
b = LI()
h = []
V = [0]*n
for i,v in enumerate(b):
    heappush(h,(-v,i))
    V[i] = v
ans = 0
while h:
    v,i = heappop(h)
    v = -v
    tmp = V[(i+1) % n] + V[i-1]
    if v == a[i]:
        continue
    s = (v - a[i])//tmp

    if s <= 0:
        print(-1)
        quit()

    ans += s
    v -= s*tmp
    V[i] = v
    if v != a[i]:
        heappush(h,(-v,i))
print(ans)


Measured memory_bytes: 123596
#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

int ans[2'009];

int main() {
  int n, x, y;
  scanf("%d%d%d", &n, &x, &y);
  --x;
  --y;
  for (int i = 0; i < n; ++i) {
    ans[i] = 0;
  }
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      ++ans[min(j - i, abs(i - x) + 1 + abs(y - j))];
    }
  }
  for (int i = 1; i < n; ++i) {
    printf("%d\n", ans[i]);
  }
}


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

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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


Measured memory_bytes: 256
x=[]
for i in range(3):
	x.append(list(map(int, input().split())))

N=int(input())

b = []
for i in range(N):
	b.append(int(input()))

for i in range(3):
	for j in range(3):
		if x[i][j] in b:
			x[i][j]=0

import numpy as np

if min(np.sum(x, axis=0))==0:
	kotae='Yes'
elif min(np.sum(x, axis=1))==0:
	kotae='Yes'
elif x[0][0]==0 and x[1][1]==0 and x[2][2]==0:
	kotae='Yes'
elif x[2][0]==0 and x[1][1]==0 and x[0][2]==0:
	kotae='Yes'
else:
	kotae='No'

print(kotae)

Measured memory_bytes: 26360
#include <bits/stdc++.h>
#include<list>
#include<algorithm>
#define ll long long int
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define rep(a,b,c) for(a=b;a<c;a++)
#define repj(a,b,c) for(a=b;a<c;a++)
#define repr for(i=n-1;i>=0;i--)
#define pii pair<ll,ll>
#define pll pair<ll, ll>
#define inf 100000001
const double pie  =3.141592653589793238463;
#define mod 1000000007
#define lb lower_bound
#define up upper_bound
#define rep1 for(i=1;i<=n;i++)
#define vr vector
#define POP(x)      __builtin_popcountll(x)
#define zerobits(x)      __builtin_ctzll(x)
#define ef else if
#define all(x) (x).begin(), (x).end()
#define SORT(A) sort(A.begin(),A.end());
#define REV(A) reverse(A.begin(), A.end());
#define lenth length()
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n" 
const ll dx[4] = { -1, 1, 0, 0};
const ll dy[4] = {0, 0, -1, 1};
ll XX[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
ll YY[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
#define precise(x) cout<<fixed<<setprecision(x)
#define t1(x)                cerr<<#x<<": "<<x<<endl
#define t2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define t3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define t4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define t5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define t6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
using namespace std;
void SieveOfEratosthenes(ll n) 
{ 
    bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (ll p=2; p*p<=n; p++) 
    { 
        if (prime[p] == true) 
        { 
            for (ll i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
  
    // for (ll p=2; p<=n; p++) 
       // if (prime[p]) 
          // cout << p << " "; 
} 
ll power(ll x, ll y, ll p)  
{  
    ll res = 1;     // Initialize result  
  
    x = x % p; // Update x if it is more than or  
                // equal to p 
   
    if (x == 0) return 0; // In case x is divisible by p; 
  
    while (y > 0)  
    {  
        // If y is odd, multiply x with result  
        if (y & 1)  
            res = (res*x) % p;  
  
        // y must be even now  
        y = y>>1; // y = y/2  
        x = (x*x) % p;  
    }  
    return res;  
}  
  
int main()
{
   fastio
   ll t,i,j,k,l,m,n,a,x,b,y,z,c,h,d,f,e,p,o,nl,np,q,r,g;
   cin>>n;
   ll brr[105];
   ll sum=0;
   ll arr[106];
   rep(i,0,n-1)
   {
    cin>>brr[i];
   }
   arr[0]=brr[0];
   arr[n-1]=brr[n-2];
   rep(i,1,n-1)
   {
       arr[i]=min(brr[i-1],brr[i]);
   }

   rep(i,0,n)
   sum+=arr[i];


   cout<<sum<<endl;

}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
typedef long long ll;
typedef pair<ll,ll> P;
const int INF=INT_MAX / 3;
const ll LINF=LLONG_MAX / 3LL;
#define CONST 1000000007
#define EPS (1e-8)
#define PB push_back
#define MP make_pair
#define sz(a) ((int)(a).size())
#define reps(i,n,m) for(int i=(n);i<int(m);i++)
#define rep(i,n) reps(i,0,n)
#define SORT(a) sort((a).begin(),(a).end())
ll mod(ll a,ll m){return (a%m+m)%m;}
int dx[9]={0,1,0,-1,1,1,-1,-1,0},dy[9]={1,0,-1,0,1,-1,1,-1,0};
ll n,m;
int main(){
  int W, a, b;
  cin >> W >> a >> b;
  int c = min(a, b);
  int d = max(a, b);
  cout << max(0, d - c - W) << endl;
  return 0;
}


Measured memory_bytes: 256
n,k=map(int,input().split())
a=list(map(int,input().split()))
l,r=0,max(a)
def test(x):
  num=0
  for i in a:
    num+=i//x
    if i%x==0:
      num-=1
  if num<=k:
    return num
while r-l>1:
  mid=(l+r)//2
  if test(mid):
    r=mid
  else:
    l=mid
print(r)

Measured memory_bytes: 30932
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>

using namespace std;

bool comp (pair<int,int> x, pair<int, int> y) {
    return x.second < y.second;
}

int main() {
    int n, m;
    cin >> n >> m;
    int i;
    vector<pair<int,int> > v(m);
    for (i = 0; i < m; i++)
        cin >> v[i].first >> v[i].second;

    sort(v.begin(), v.end(), comp);
    int endline = 0;
    int ans = 0;

    for (i = 0; i < m; i++) {
        if (v[i].first >= endline) {
            ans++;
            endline = v[i].second;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1024
// 失敗するからこそ そこから立ち向かって行く強さがあってそんな強さが本当の強さだと私は思うから
#ifdef DAIJOBU
#include "/home/v-o_o-v/deb.h"
#define deb(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#include <bits/stdc++.h>
#define deb(x...)
#endif 

using namespace std;

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef long long lint;
typedef double ld;

void a();void b();void c();void d();void e();void f();

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

	// a();
	// b();
	// c();
	// d();
	e();
	// f();
	return 0;
}

void a(){
	string s;
	cin >> s;
	if(s == "ABC")puts("ARC");
	else puts("ABC");
}

void b(){
	int n, k;
	cin >> n >> k;
	vi adj[1500];
	forn(i, k){
		int d;
		cin >> d;
		forn(j, d){
			int x;
			cin >> x;
			adj[x].pb(i);
		}
	}
	int c = 0;
	for1(i, n){
		if(adj[i].size() == 0)c++;
	}
	cout << c;
}

void c(){
	vi adj[100050];
	int n, m;
	cin >> n >> m;
	vi ht(n + 1);
	for1(i, n)cin >> ht[i];
	forn(i, m){
		int a, b;
		cin >> a >> b;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	int c = 0;
	for1(i, n){
		bool ok = true;
		for(auto j:adj[i]){
			if(ht[i] <= ht[j])ok = false;
		}
		if(ok)c++;
	}
	cout << c;
}

void d(){
	lint x;
	cin >> x;
	bool ok = true;
	for(lint i = -1e3;; i++){
		lint b = i * i * i * i * i - x;
		for(lint j = -1e3; j <= 1e3; j++){
			if(j * j * j * j * j == b){
				ok = true;
				cout << i << ' ' << j;
				return;
			}
		}
	}
	assert(ok == true);
}

void e(){
	int n;
	cin >> n;
	int a[n];
	map<lint, lint> m1, m2;
	forn(i, n){
		cin >> a[i];
		m1[a[i] + i]++;
		m2[i - a[i]]++;
	}
	lint ans = 0;
	for(auto i:m1){
		ans += (i.se * m2[i.fi]);
	}
	cout << ans;
}

void f(){

}


Measured memory_bytes: 38660
n,q=map(int,input().split())
s=input()
x=[0]*n

for i in range(n-1):
    if s[i:i+2]=="AC":
        x[i+1]=x[i]+1
    else:
        x[i+1]=x[i]
for i in range(q):
    l,r=map(int,input().split())
    print(x[r-1]-x[l-1])


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

#define pb push_back
#define rep(i, a, n) for(int (i)=a; (i)<(n); (i)++)
#define FOR(i, n) rep(i, 0, n)
#define F(n) FOR(i, n)
#define FF(n) FOR(j, n)
#define repi(i, a, n) for(int (i)=a; (i)<=(n); (i)++)
#define FORI(i, n) repi(i, 1, n)
#define FI(n) FORI(i, n)
#define FFI(n) FORI(j, n)
#define IN(x) int x; cin>>(x);
#define SIN(x) string x; cin>>x;
#define INN(x, y) int x, y; cin>>(x)>>(y);
#define INFO(a) cout<<"info "<<a<<endl
#define vi vector<int>
#define vll vector<ll>
#define pii pair<int, int>
#define vpii vector<pair<int, int> >
#define sortv(x) sort((x).begin(), (x).end())
#define sortvd(x) sort((x).begin(), (x).end(), greater<int>())
#define lboundv(x,v) lower_bound((x).begin(),(x).end(),(v))-(x).begin();
#define uboundv(x,v) upper_bound((x).begin(),(x).end(),(v))-(x).begin();
#define ite iterator
#define fi first
#define se second
#define mems(a, v) memset((a), (v), sizeof((a)))
#define lmid(l, r) ((l)+(r)-1)/2
#define rmid(l, r) ((l)+(r))/2+1
#define mp make_pair

typedef long long ll;
typedef long double LD;

using namespace std;

#define N 500005
int main() {
	ios::sync_with_stdio(0);
	SIN(s);
	F(s.size()-1) {
		if(s[i]=='A' && s[i+1]=='C') {cout<<"Yes"<<endl; return 0;}
	}
	cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;
 
 
public class Main {

	static long MOD = 1_000_000_007;
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		//int N = Integer.parseInt(sc.next());
		//long L = Long.parseLong(sc.next());

		Scanner sc = new Scanner(System.in);
		//char[] c = sc.next().toCharArray();
		int N = Integer.parseInt(sc.next());
		int L = Integer.parseInt(sc.next());
		int INF = Integer.MAX_VALUE;
		int INF_MIN = -1000;//Integer.MIN_VALUE;
		
		int min = INF;
		int min_ = INF;
		int sum = 0;
		for(int i=0; i<N; i++){
			if(min > Math.abs(L+i)){
				min = Math.abs(L+i);
				min_ = L+i;
			}

			sum += L+i;
		}
		int ans = sum - min_;

		System.out.println(ans);
		
		
	
		
		
	}
}



Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
vector<vector<ll>> tree(200010, vector<ll>());
vector<ll> cnts(200010, 0);
 
void dfs(int n, ll x, int parent)
{
  cnts[n] += x;
  for (auto v:tree[n]) {
    if (v == parent) continue;
    dfs(v, cnts[n], n);
  }
}
 
int main()
{
  ll N;
  scanf("%lld",&N);
  ll Q;
  scanf("%lld",&Q);
  for(int i=0; i<N-1; i++){
    ll a,b;
    scanf("%lld",&a);
    scanf("%lld",&b);
    a--; b--;
    tree[a].push_back(b);
    tree[b].push_back(a);
  }
  for (int i=0; i<Q; i++){
    ll p,x;
    scanf("%lld",&p);
    scanf("%lld",&x);
    p--;
    cnts[p] += x;
  }
  dfs(0, 0, -1);
  for (int i=0; i<N; i++) {
    if (i==0) cout << cnts[i];
    else cout << " " << cnts[i];
  }
  cout << endl;
 
  return 0;
}

Measured memory_bytes: 24320
#include<iostream>
using namespace std;
int main() {
	int Q;
	int c, a, n, ans[111], an;
	cin >> Q;
	an = 0;
	for (int i = 1; i <= Q; i++) {
		cin >> c >> a >> n;
		an = an + 1;
		ans[an] = 0;
		while (1) {
			if (c == 0 || a == 0 || n == 0) {
				goto a;
			}
			c = c - 1;
			a = a - 1;
			n = n - 1;
			ans[an] = ans[an] + 1;
		}
	a:;
		while (1) {
			if (c <= 1 || a <= 0) {
				goto b;
			}
			c = c - 2;
			a = a - 1;
			ans[an] = ans[an] + 1;
		}
	b:;
		while (1) {
			if (c <= 2) {
				goto c;
			}
			c = c - 3;
			ans[an] = ans[an] + 1;
		}
	c:;
	}
	for (int i = 1; i <= an; i++) {
		cout << ans[i] << endl;
	}
}


Measured memory_bytes: 3104
#include<stdio.h>
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include<stack>
#include <queue>
#include<map>
#include <set>
#include<math.h>
using namespace std;
#define int long long
#define ll long long
#define double long double
#define rep(i,n) for(ll i=0;i<n;++i)
#define loop(i,m,n) for(ll i=m;i<n;++i)
#define ggr getchar(); getchar();return 0;
#define pie 3.141592653589793238462643383279
#define INF 1000000007
#define elif else if
int bin(int bina) {
	int ans = 0;
	for (int i = 0; bina > 0; i++)
	{
		ans = ans + (bina % 2) * pow(10, i);
		bina = bina / 2;
	}
	return ans;
}
bool prime(int n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n % i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int jo(int n) {
	int ans = 1;
	rep(i, n) {
		ans *= 2;
	}
	return ans;
}
int a[5],b[5],ans=0;
signed main() {
	rep(i, 5) {
		cin >> a[i];
		b[i] = a[i] % 10;
	}
	int sum=10;
	rep(i, 5) {
		if (b[i] == 0)continue;
		else if(b[i]<sum) sum = b[i];
	}
	rep(i, 5) {
		if (a[i] % 10 == 0)ans += a[i] / 10;
		else ans += (a[i] / 10) + 1;
	}
	cout << (ans - 1) * 10 + sum << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args){

		Scanner sc = new Scanner(System.in);
        
		int N = sc.nextInt();
      
		String S = sc.next();
        String T = sc.next();          
 
      int i = 0;

      char[] Schar =  S.toCharArray();
      char[] Tchar =  T.toCharArray();
      
      for (i=0; i < N; i++) {
      System.out.print(Schar[i]);
      System.out.print(Tchar[i]);  
      } 
	
	return;

	}
}

Measured memory_bytes: 21076
n , t = map(int,input().split())
for i in range(n+1):
    for j in range(n+1-i):
        k = n - i- j

        #for k in range(n+1-i-j):#このfor分は不要、i,jで決まるから
        if 10000 * i + 5000 * j + 1000 * k == t:

            print('{} {} {}'.format(i, j ,k))
            exit(0)
print('{} {} {}'.format(-1 ,-1,-1))


Measured memory_bytes: 2940
H,W=map(int,input().split())
S=[list(input()) for _ in range(H)]
dx=[-1,0,1,-1,1,-1,0,1]
dy=[-1,-1,-1,0,0,1,1,1]

for i in range(H):
  for j in range(W):
    if S[i][j]=='.':
      num=0
      for (x,y) in zip(dx,dy):
        if 0<=i+x<H and 0<=j+y<W and S[i+x][j+y]=='#':
          num+=1
      S[i][j]=str(num)

for s in S:
  print(''.join(s))

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

int main(){
  double a,b,c,d,e;
  cin>>a>>b>>c>>d;
  e=2.000000;
  cout<<a*b/e<<" ";
  if(c==a/e&&d==b/e)
    cout<<1<<endl;
  else
    cout<<0<<endl;
  }

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

int main() {
    int a, p;
    cin >> a >> p;

    cout << (a * 3 + p) / 2 << endl;

    return 0;
}

Measured memory_bytes: 256
#include <cstdio>

int main()
{
	int n, k;
	scanf("%d%d", &n, &k);
	int i;
	int count;
	for (i = 0, count = 0; i < n; i++) {
		int h;
		scanf("%d", &h);
		if (h >= k)
			count++;
	}
	printf("%d\n", count);
}


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

int main(){
	int n;
	int sosu[100000];
	int snum;
	bool judge;

	sosu[0] = 2;

	while(cin >> n){
		snum = 0;
		for(int i = 3; i <= n; i++){
			judge = true;
			for(int j = 0; sosu[j]*sosu[j] <= i; j++){
				if(i%sosu[j] == 0){
					judge = false;
					break;
				}
			}
			if(judge == true){
				snum ++;
				sosu[snum] = i;
			}
		}
		if(n == 1){
			cout << 0 << endl;
		}else{
			cout << snum + 1 << endl;
		}
	}



	return(0);
}

Measured memory_bytes: 1472