akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int main(){
    int N;
    vector <int> a;
    int ana = INT_MAX;
    bool judge = false;
    int here = 1;
    
    a.push_back(0);
    cin >> N;
    int sub;
    for(int i = 0; i < N; i++){
        cin >> sub;
        a.push_back(sub);
    }
    
    int cnt = 0;
    while(cnt < 100000){
        here = a[here];
        cnt++;
        if(here == 2){
            judge = true;
            break;
        }
    }
    
    if(judge){
        cout << cnt << endl;
    }
    else{
        cout << -1 << endl;
    }
}

Measured memory_bytes: 892
using System.Linq;
using System.Collections.Generic;
using System;

public class Hello
{
    public static void Main()
    {
        var a = new List<int>();
        GeneratePrime(a, 104730);
        var b = new int[10000];
        b[0] = a[0];
        for (int i = 1; i < 10000; i++)
            b[i] = a[i] + b[i - 1];
        while (true)
        {
            var n = int.Parse(Console.ReadLine().Trim());
            if (n == 0) break;
            Console.WriteLine(b[n - 1]);
        }
    }
    public static void GeneratePrime(List<int> primeList, int m)
    {
        int prime;
        var sqrtMax = Math.Sqrt(m);
        var searchList = Enumerable.Range(2, m - 1).ToList();
        do
        {
            prime = searchList.First();
            primeList.Add(prime);
            searchList.RemoveAll(n => n % prime == 0);
        }
        while (prime < sqrtMax);
        primeList.AddRange(searchList);
    }
}

Measured memory_bytes: 10432
{-# LANGUAGE FlexibleInstances    #-}
{-# LANGUAGE TypeSynonymInstances #-}

import           Control.Applicative
import           Control.DeepSeq
import           Control.Monad
import           Control.Monad.ST
import qualified Data.Array                  as A
import qualified Data.Array.IArray           as IA
import qualified Data.Array.IO               as AI
import qualified Data.Array.MArray           as MA
import qualified Data.Array.ST               as STA
import qualified Data.Array.Unboxed          as AU
import           Data.Bits
import qualified Data.ByteString.Char8       as BS
import           Data.Char
import qualified Data.Graph                  as G
import           Data.Int
import qualified Data.IntMap                 as IM
import qualified Data.IntSet                 as IS
import           Data.List
import qualified Data.Map.Strict             as M
import           Data.Maybe
import           Data.Ord
import qualified Data.Sequence               as SQ
import qualified Data.Set                    as S
import           Data.Time
import qualified Data.Tree                   as T
import qualified Data.Vector                 as V
import qualified Data.Vector.Mutable         as VM
import qualified Data.Vector.Unboxed         as VU
import qualified Data.Vector.Unboxed.Mutable as VUM

readInt :: IO [Int]
readInt = map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine

readInts :: Int -> IO [[Int]]
readInts n = replicateM n readInt

readInteger :: IO [Integer]
readInteger = map (fst . fromJust . BS.readInteger) . BS.words <$> BS.getLine

readIntegers :: Int -> IO [[Integer]]
readIntegers n = replicateM n readInteger

readString :: IO [String]
readString = map BS.unpack . BS.words <$> BS.getLine

readStrings :: Int -> IO [[String]]
readStrings n = replicateM n <$> readString

toPair :: [a] -> (a, a)
toPair [x, y] = (x, y)

count :: Eq a => a -> [a] -> Int
count a as = length $ filter (== a) as

put :: Show a => a -> IO ()
put = putStr . show

putLn :: Show a => a -> IO ()
putLn = print

putList :: Show a => [a] -> IO ()
putList [n] = put n
putList (n:ns) = do
  put n
  putStr " "
  putList ns

putStrList :: [String] -> IO ()
putStrList [n] = putStr n
putStrList (n:ns) = do
  putStr n
  putStr " "
  putStrList ns

main = do
  [n] <- readInt
  put $ lcm n 2


Measured memory_bytes: 380
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;



int main() {
    ios_base::sync_with_stdio(false);
    int r;
    cin >> r;
    if(r < 1200)
        cout << "ABC" << endl;
    else if(r < 2800)
        cout << "ARC" << endl;
    else if(r >= 2800)
        cout << "AGC" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
string s;
bool ok(string t)
{
	string r=t;
	reverse(t.begin(),t.end());
	return r==t;
}
int main()
{
	cin>>s;
	int n=s.size();
	if(ok(s)&&ok(s.substr(0,n/2))&&ok(s.substr(n/2+1,n/2)))
		puts("Yes");
	else
		puts("No");
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef string str;
typedef vector<ll> vel;
typedef vector<str> ves;
#define REP(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
#define rep(i, b) REP(i, 0, b)

int main() {
    ll a, b, c;
    cin >> a >> b >> c;
    ll count = 0;
    if (a == b && b == c && c == a) {
        count = 1;
    }
    else {
    if (a != b) {
        count ++;
    }
    if (b != c) {
        count ++;
    }
    if (c != a) {
        count ++;
    }
    }
    cout << count << endl;
}

Measured memory_bytes: 256
#include <vector> 
#include <list> 
#include <map> 
#include <set> 
#include <deque> 
#include <queue> 
#include <stack> 
#include <bitset> 
#include <algorithm> 
#include <functional> 
#include <numeric> 
#include <utility> 
#include <sstream> 
#include <iostream> 
#include <iomanip> 
#include <cstdio> 
#include <cmath> 
#include <cstdlib> 
#include <cctype> 
#include <string> 
#include <cstring> 
#include <ctime> 

using namespace std;

#define _int64 long long
#define mo 1000000007

int c[4100][4100];

int main()
{
  int i,j,k,a,b,ans,tmp;
  for (i=0;i<4100;i++)
  {
    c[i][0]=1;
    c[i][i]=1;
    for (j=1;j<i;j++)
    {
      c[i][j]=c[i-1][j-1]+c[i-1][j];
      if (c[i][j]>=mo) c[i][j]-=mo;
    }
  }
  scanf("%d%d",&a,&b);
  ans=0;
  for (i=1;i<=b;i++)
  {
    if (b-i==0)
    {
      ans+=a+1;
      if (ans>=mo) ans-=mo;
      //cout<<i<<" "<<ans<<endl;
      continue;
    }
    
    for (j=1;j<=b-i;j++)
    {
      tmp=a-(b-i)-(b-i-j);
      if (tmp<0) continue;
      ans+=(_int64)c[b-1][i-1]*c[b-i-1][j-1]%mo*c[tmp+2][2]%mo;
      if (ans>=mo) ans-=mo;
      //cout<<i<<" "<<j<<" "<<ans<<endl;
    }
  }
  printf("%d\n",ans);
  return 0;
}

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

int main(){
  int N;
  cin>>N;
  string S;
  cin>>S;
  for(int i=0;i<S.size();++i){
    int x=0;
    x=S.at(i)-'A';
    x=(x+N)%26;
    S.at(i)='A'+x;
  }
  cout<<S<<endl;
}

Measured memory_bytes: 256
a, b = map(int, input().split())

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(n**0.5) + 1):
        if n % k == 0:
            return False

    return True

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors
L = make_divisors(a)
cv=[]
for i in range(len(L)):
	if b % L[i] == 0:
		cv.append(L[i])
cnt=1
cv=set(cv)
for d in cv:
	if is_prime(d):
		cnt+=1
print(cnt)


Measured memory_bytes: 4012
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i, a, b) for(ll i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define whole(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
using P = pair<ll, ll>;
#define debug(var) cerr << "[" << #var << "] " << var << endl
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
const ll mod = 1000000007;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};


int main(){
    ll n;
    cin >> n;
    vector<ll> a(n+1);
    rep(i, n+1) cin >> a[i];
    if (a[0]!=0) {
        if (a[0]==1 && n==0) {
            cout << 1 << endl;
        }
        
        else {
            cout << -1 << endl;
        }
        return 0;
    }
    ll ans = 0;
    vector<ll> num(n+1);
    for (ll i=n; i>=0; i--) {
        //ans += a[i] * (i+1);
        if (i==n) num[i] = a[i];
        else num[i] = num[i+1] + a[i];
    }
    for (ll i=0; i<n; i++) {
        if (i==0) {
            //ans -= (num[i]-1);
            num[i] = 1;
            continue;
        }
        ll limit = (num[i-1]-a[i-1])*2LL;
        ll prev = num[i];
        num[i] = min(num[i], limit);
        if (num[i]<=a[i]) {
            cout << "-1" << endl;
            return 0;
        }
        if (i==n-1) {
            if (num[i]-a[i]>a[n]) num[i] = a[i]+a[n];
            
            if ((num[i]-a[i])*2<a[n]) {
                cout << "-1" << endl;
                return 0;
            }
            
        }
        //ans -= (prev-num[i]);
    }
    rep(i, n+1) {
        ans += num[i];
    }
    
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4844
#[allow(unused_macros)]
macro_rules! scan {
    () => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().to_string()
        }
    };
    (;;$n:expr) => {
        (0..$n).map(|_| scan!()).collect::<Vec<_>>()
    };
    ($t:ty) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty;;) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|t| t.parse::<$t>().unwrap())
                .collect::<Vec<_>>()
        }
    };
    ($t:ty;;$n:expr) => {
        (0..$n).map(|_| scan!($t;;)).collect::<Vec<_>>()
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
                    scan!($t)
        ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
                    scan!($($t),*)
        ).collect::<Vec<_>>()
    };
}

fn clear_all(monsters: &[i64], a: i64, b: i64, n: i64) -> bool {
    let mut num = 0;
    for i in monsters.iter() {
        if i - n * b >= 0 {
            num += ((i - n * b) + (a - b) - 1) / (a - b)
        }
    }
    num <= n
}

fn main() {
    let (n, a, b) = scan!(i64, i64, i64);
    let monsters = scan!(i64;n);

    let mut left = 0;
    let mut right = 1_000_000_000;
    while left < right - 1 {
        let mid = (left + right) / 2;
        if clear_all(&monsters, a, b, mid) {
            right = mid;
        } else {
            left = mid;
        }
    }
    println!("{}", right);
}


Measured memory_bytes: 4352
#include<stdio.h>
int main(void)
{
	int i,n,a[21],b[21],num,max;
	scanf("%d",&n);
	for(i=1;i<=n;i++) {
		scanf("%d %d",&a[i],&b[i]);
	}
	max=-1;
	num=1000;
	for(i=1;i<=n;i++) {
		if(max<b[i]) {
			max=b[i];
			num=a[i];
		}
		else if(max==b[i]) {
			if(a[i]<num) {
				num=a[i];
			}
		}
	}
	printf("%d %d\n",num,max);
	return 0;
}

Measured memory_bytes: 600
#define _GLIBCXX_DEBUG
    #include <bits/stdc++.h>
    using namespace std;
    #define vec vector
    #define fi first
    #define se second
    #define eb emplace_back
    #define ef emplace_front
    #define pof pop_front()
    #define pob pop_back()
    #define Rep(i,n) for(li i=0,nn=(li)(n);i!=nn;++i)
    #define Rep1(i,n) for(li i=1,nn=(li)(n)+1;i!=nn;++i)
    #define Size(v) (li)(v.size())
    #define SortA(v) sort(v.begin(),v.end())
    #define SortD(v) sort(v.rbegin(),v.rend())
    #define All(a) (a).begin(),(a).end()
    #define Input(a) for(li ii=0,nn=(li)(a.size());ii!=nn;++ii){cin>>(a).at(ii);}
    #define Input2(a,b) for(li ii=0,nn=(li)(a.size());ii!=nn;++ii){cin>>(a).at(ii)>>(b).at(ii);}
    #define mp make_pair
    using li = int64_t;
    using intl = int64_t;
    using vi = vec<li>;
    using vb = vec<bool>;
    using vvi = vec<vi>;
    using qi = deque<li>;
    using pi = pair<li,li>;
    using vpi = vec<pi>;
    using si = set<li>;
    using vsi = vec<si>;
    using mii = map<li,li>;
    using vmii = vec<mii>;
    vec<li> dx = {0, 1, 0, -1, 1, 1, -1, -1};
    vec<li> dy = {1, 0, -1, 0, 1, -1, 1, -1};
    constexpr li INF = 9223372036854775807;
     
    void Yes(li b){
      if(b)cout<<"Yes";
      else cout<<"No";
    }
    void yes(li b){
      if(b)cout<<"yes";
      else cout<<"no";
    }
     
    int main(){
      std::ios::sync_with_stdio(false);
      std::cin.tie(0);
     
      li N,D,A,X,H;
     
      cin >>N>>D>>A;
     
      vpi XH(N);
     
      Rep(i,N){
      	cin>>X>>H;
      	XH[i].fi=X;
      	XH[i].se=H;
      }
     
      SortA(XH);
     
      deque<pi> bend;
      li ans =0;
      li bomb =0;
     
      for(auto&& xh:XH){
      	while(!bend.empty() && bend.front().fi < xh.fi ){
      		bomb -= bend.front().se;
      		bend.pof;
      	}
      	xh.se -= bomb;
      	if(xh.se<=0){continue;}
      	ans += (xh.se +A -1)/A;
      	bomb += (xh.se +A -1)/A *A;
      	bend.eb(xh.fi +2*D, (xh.se +A -1)/A*A);
      }
     
      cout <<ans;
    }

Measured memory_bytes: 7896
// general helpers
const debug = (message?: any, ...optionalParams: any[]) => {
  if (process.env.LOCAL_DEBUG === '1') console.log(message, ...optionalParams)
}

// helpers
const parseLines = (
  lines: string[]
): any => {
  const N = +lines[0]
  const d = lines.slice(1, 1 + N).map(n => +n)
  const obj = { N, d }
  debug(obj)
  return obj
}

// solver
export const solve = (lines: string[]): string => {
  const { N, d } = parseLines(lines)
  d.sort((a: number, b: number) => b - a)
  let count = 1
  let min = d[0]
  for (let i = 1; i <= d.length; i++) {
    if (d[i] < min) {
      min = d[i]
      count++
    }
  }
  return `${count}`
}

// main
const main = (lines: string[]) => {
  console.log(solve(lines))
}

// exec main function for submit
if (process.env.LOCAL_DEBUG !== '1') {
  const { stdin: input, stdout: output } = process
  input.resume()
  input.setEncoding('utf8')
  const lines: string[] = []
  require('readline')
    .createInterface({ input, output })
    .on('line', (line: string) => lines.push(line))
    .on('close', () => main(lines))
}


Measured memory_bytes: 7756
#include <bits/stdc++.h>
using namespace std;
int main(){
    int A,B,C;
    cin >> A >> B >> C;
    int ans;
    if (A <= B && A <= C){
        if(B <= C){
            ans = C - A;
        }else{
            ans = B - A;
        }
    }else if (A >= B && A >= C){
        if(B <= C){
            ans = A - B;
        }else{
            ans = A - C;
        }
    }else if(B <= C){
        ans = C - B;
    }else{
        ans = B - C;
        }
cout << ans << endl;
}

Measured memory_bytes: 256
using System;
using System.Text;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;
using System.Threading.Tasks;
class Program
{
	static void Main(string[] args)
	{
		const int mod = 1000000007;
		int N = int.Parse(Console.ReadLine());
		var A = Console.ReadLine().Split().Select(x=>int.Parse(x)).ToArray();
		int ans = 1;
		Array.Sort(A);
		int[] compare = new int[N];
		int adding = N - 1;
        for(var i = 0; i < N; i++)
		{
			if (i % 2 == 0)
			{
				compare[i] = adding;
			}
			if (i % 2 == 1)
			{
				compare[i] = adding;
				adding -= 2;
			}
		}
		Array.Sort(compare);
		bool b = true;
        for(var i = 0; i < N; i++)
		{
			if (A[i] != compare[i])
			{
				b = false;
				ans = 0;
				break;
			}

		}
		if (b)
		{
            for(var i = 0; i < N / 2; i++)
			{
				ans = (ans * 2) % mod;
			}
		}

		Console.WriteLine(ans);

	}
}


Measured memory_bytes: 18528
S = input().strip()
first = int(S[:2])
second = int(S[2:])

def isMonth(n):
  return 1 <= n <= 12

if isMonth(first) and isMonth(second):
  print('AMBIGUOUS')
elif not(isMonth(first)) and isMonth(second):
  print('YYMM')
elif isMonth(first) and not(isMonth(second)):
  print('MMYY')
else:
  print('NA')

Measured memory_bytes: 3060
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<vector<int> > vvi;
typedef vector<int> vi;
typedef vector<string> vs;

/*
struct node {
	int key;
	node* parent;
	node* left;
	node* right;
};
typedef vector<node> vn;
void pre(int u, vn& A) {
	if (u == -1) return;
	cout <<" "<<u ;
	pre(A[u].left,A);
	pre(A[u].right,A);
}
void in(int u, vn& A) {
	if (u == -1)return;
	in(A[u].left, A);
	cout <<" "<< u ;
	in(A[u].right, A);
}
void post(int u, vn& A) {
	if (u == -1)return;
	post(A[u].left, A);
	post(A[u].right, A);
	cout<<" " << u ;
}
void print(int root) {
	in(root);
	pre(root);
}
void insert() {

}
int main() {
	int N;
	cin >> N;
	vector<node> A(N);
	for (int i = 0; i < N; i++)A[i].parent = A[i].left = A[i].right = -1;
	for (int i = 0; i < N; i++)
	{
		int id;
		cin >> id;
		cin >> A[id].left;
		cin >> A[id].right;
		if (A[id].left != -1)A[A[id].left].parent = id;
		if (A[id].right != -1)A[A[id].right].parent = id;
	}
	int root = 0;
	for (int i = 0; i < N; i++)
	{
		if (A[i].parent == -1)root = i;
	}

};

*/
int main() {
	int N;
	cin >> N;
	vector<int> A(N);
	vector<int> B(N);
	vector<int> C(N);
	for (int i = 0; i < N; i++)cin >> A[i];
	for (int i = 0; i < N; i++)cin >> B[i];
	for (int i = 0; i < N; i++)cin >> C[i];
	sort(A.begin(), A.end());
	sort(B.begin(), B.end());
	sort(C.begin(),C.end());
	ll count = 0;
	for (int b = 0; b < N; b++)
	{

		int Alen=(lower_bound(A.begin(), A.end(), B[b])-A.begin());
		int Clen=(C.end()-upper_bound(C.begin(),C.end(),B[b]));
		//cout << Alen << Clen << endl;
		count += (ll)Alen * (ll)Clen;
	}
	cout << count << endl;
}

Measured memory_bytes: 1408
#!/usr/bin/env python3
import string


def main():
    S = input()
    S_temp = S
    ans_temp = 'zyxwvutsrqponmlkjihgfedcba'
    for i in range(len(S) + 1):
        for c in string.ascii_lowercase:
            if c not in S[:i]:
                S_temp = S[:i] + c
                if S < S_temp:
                    break
        if S < S_temp and S_temp < ans_temp:
            ans_temp = S_temp
    print(ans_temp if S < ans_temp else -1)


if __name__ == "__main__":
    main()


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

int main(){
    while(1){
        int n; cin>>n;

        if(n==0)break;

        vector<pair<int,int> > area;

        for(int i=0; i<n; i++){
            int xd,yd; cin>>xd>>yd;
            area.push_back(make_pair(xd,yd));
        }

        int m; cin>>m;

        int x=10,y=10,count = 0;

        vector<vector<bool> > check(21,vector<bool>(21,false));

        for(int i=0; i<m; i++){
            char dir; int masu;

            cin>>dir>>masu;

            if(dir == 'N'){
                for(int j=y; j<=y+masu; j++){
                    check[x][j] = true;
                }
                y+=masu;
            }

            else if(dir == 'S'){ 
                for(int j=y; j>=y-masu; j--){
                    check[x][j] = true;
                }
                y -= masu;
            }

            else if(dir == 'W'){
                for(int j=x; j>=x-masu; j--){
                    check[j][y] = true;
                }
                x -= masu;
            }

            else if(dir == 'E'){
                for(int j=x; j<=x+masu; j++){
                    check[j][y] = true;
                }
                x += masu;
            }
        }

        for(int j=0; j<area.size(); j++){
            int ax = area[j].first,ay=area[j].second;
                
            if(check[ax][ay]) count++;
        }

        if(count == n) cout<<"Yes"<<endl;

        else cout<<"No"<<endl;

    }

    return 0;
}


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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second

using vint=vector<int>;
using pint=pair<int,int>;
using vpint=vector<pint>;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

template<class A,class B>
ostream& operator<<(ostream& ost,const pair<A,B>&p){
    ost<<"{"<<p.first<<","<<p.second<<"}";
    return ost;
}

template<class T>
ostream& operator<<(ostream& ost,const vector<T>&v){
    ost<<"{";
    for(int i=0;i<v.size();i++){
        if(i)ost<<",";
        ost<<v[i];
    }
    ost<<"}";
    return ost;
}

inline int topbit(unsigned long long x){
    return x?63-__builtin_clzll(x):-1;
}

inline int popcount(unsigned long long x){
    return __builtin_popcountll(x);
}

inline int parity(unsigned long long x){
    return __builtin_parity(x);
}

signed main(){
    int K,X;
    cin>>K>>X;
    if(K*500>=X)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

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

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end() 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

long long INF=LLONG_MAX;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
	string s,t; cin >> s >> t;
	int ans = 0;
	for(int i = 0; i < 3; i++)if(s[i]==t[i])ans++;
	cout << ans << endl;
}	


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof a)
#define mcpy(a,b) memcpy(a,b,sizeof b)
#define lb(x) ((x)&(-(x)))
#define xx first
#define yy second
#define pb push_back
#define mp make_pair
#define pii pair<int,int> 
#define dalao 1000000007
#define inf 0x3f3f3f3f
#define N 305
using namespace std;
typedef long long ll;
int n,m,f[N][N][N];
inline void upd(int& a,int b){a=a+b>=dalao?a+b-dalao:a+b;}
int main(){
	cin>>n>>m,f[0][1][1]=1;
	for(int i=0;i<m;i++)for(int j=1;j<=n;j++)for(int k=1;k<=j;k++)if(f[i][j][k])
		upd(f[i+1][j+1][k],1ll*f[i][j][k]*(n-j)%dalao),
		upd(f[i+1][j][k],1ll*f[i][j][k]*(j-k)%dalao),
		upd(f[i+1][j][j],1ll*f[i][j][k]*k%dalao);
	printf("%d",f[m][n][n]);
	return 0;
}

Measured memory_bytes: 108800
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

const double BIGNUM=400.0;

int heights[40];

int main(){

    int r,n;
    while(scanf("%d%d",&r,&n)&&r!=0){
        for(int i=0;i<40;i++) heights[i]=0;
        for(int i=0;i<n;i++){
            int l,r,h;
            scanf("%d%d%d",&l,&r,&h);
            for(int k=l+20;k<r+20;k++) heights[k]=max(heights[k],h);
        }

        double ans=BIGNUM;
        for(int i=20-r;i<20;i++){
            int dist=20-i-1;
            double depth=sqrt((double)(r*r-dist*dist));
            // printf("depth=%lf,dist=%d\n",depth,dist);
            ans=min(ans,(heights[i]+r-depth));
            // printf("ans=%lf\n",ans);
        }

        for(int i=20;i<20+r;i++){
            int dist=i-20;
            double depth=sqrt((double)(r*r-dist*dist));
            // printf("depth=%lf,dist=%d\n",depth,dist);
            ans=min(ans,(heights[i]+r-depth));
            // printf("ans=%lf\n",ans);
        }

        printf("%lf\n",ans);
    }


    return 0;
}


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


#define FAST_IO ios_base::sync_with_stdio(false), cin.tie(nullptr)
using namespace std;

signed main() {
    FAST_IO;

    int n;
    cin >> n;
    int jumps[n];
    vector<int> dp(n, 0); // dp[i] : Minimum cost for the frog to reach position i.
    for (int i = 0; i < n; i++) cin >> jumps[i];
    dp[1] = abs(jumps[1] - jumps[0]); // Base value
    for (int i = 2; i < n; i++)
        dp[i] = min(abs(jumps[i] - jumps[i - 1]) + dp[i - 1], abs(jumps[i] - jumps[i - 2]) + dp[i - 2]);
    cout << dp[n - 1];
    return 0;
}

Measured memory_bytes: 1024
#include <algorithm>
#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 rep(i,n) for(ll i=0;i<n;++i)
#define Rep(i,n) for(ll i=1;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 elif else if
#define P pair<ll,ll>
#define prique priority_queue<ll>
const int mod = 1000000007;
const int mod2 = 998244353;
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 kai(int x) {
	if (x == 0)return 1;
	return kai(x - 1) * x % mod;
}
int mod_pow(int x, int y, int mod) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % mod;
		}
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}
long nCr(int n, int r) {
	int ans = 1;
	for (ll i = n; i > n - r; --i) {
		ans = ans * i;
	}
	for (ll i = 1; i < r + 1; ++i) {
		ans = ans / i;
	}
	return ans;
}
struct union_find {
	int par[200010], size_[200010];
	void init(int x) {
		rep(i, x) { par[i] = i; size_[i] = 1; }
	}
	int find(int x) {
		if (par[x] == x)return x;
		return par[x] = find(par[x]);
	}
	void unite(int x, int y) {
		x = find(x); y = find(y);
		if (x == y)return;
		if (size_[x] < size_[y]) {
			par[x] = y;
			size_[y] += size_[x];
		}
		else {
			par[y] = x;
			size_[x] += size_[y];
		}
	}
};

signed main() {
	int n;
	cin >> n;
	int ans = n*2;
	for (int i = 1; i * i <= n; i++) {
		if (n % i == 0) {
			if (i + n / i < ans) {
				ans = i + n / i;
			}
		}
	}
	cout << ans - 2 << endl;
}

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

    int A, B;
    A = X/500;          // 500円玉の枚数
    B = (X-A*500)/5;    // 5円玉の枚数

    cout << 1000*A + 5*B << endl;
    

}

Measured memory_bytes: 256
#include <stdio.h>
    
#define PutChar(c) ; *p = (char)(c); ++p;
    
#define MAX_N (2000001)
#define MAX_Ai (10001)
#define STR_SIZE (10000010)
    
int getNum(void);
void putNum(int n);
void CountingSort(int A[], int B[], int k, int len);
    
int A[MAX_N];
int B[MAX_N];
char str[STR_SIZE];
char *p = str;
    
int main(void) {
    register int i;
    int n;
    
    fread(str, 1, STR_SIZE, stdin);
        
    n = getNum();
    for (i = 1; i <= n; ++i) {
        A[i] = getNum();
    }
        
    CountingSort(A, B, MAX_Ai, n);
        
    p = str;
    --n;
    for (i = 1; i <= n; ++i) {
        putNum(B[i]);
        PutChar(' ');
    }
    putNum(B[i]);
    PutChar('\0');
        
    puts(str);
        
    return 0;
}
    
int getNum(void) {
    int n = 0;
    while ((*p >= '0') && (*p <= '9')) {
        n = n * 10 + (int)(*p - '0');
        ++p;
    }
    ++p;
    return n;
}
    
void putNum(int n) {
    int d;
    if (n < 10) {
        PutChar('0' + n);
        return;
    }
    d = n / 10;
    if (d) putNum(d);
    PutChar('0' + (n - (d * 10)));
}
    
void CountingSort(int A[], int B[], int k, int len) {
    int C[MAX_Ai] = { 0 };
    int i, j;
    for (j = 1; j <= len; ++j) {
        ++C[A[j]];
    }
    for (i = 1; i <= k; ++i) {
        C[i] += C[i - 1];
    }
    for (j = len; j > 0; --j) {
        B[C[A[j]]] = A[j];
        --C[A[j]];
    }
}

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

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

int main() {
	std::string s;
	std::cin >> s;
	int k = ri();
	
	std::vector<std::string> all;
	for (int i = 0; i < (int) s.size(); i++) {
		std::string cur;
		for (int j = 1; j <= (int) s.size() - i && j <= k; j++) {
			cur.push_back(s[i + j - 1]);
			all.push_back(cur);
		}
	}
	std::sort(all.begin(), all.end());
	all.erase(std::unique(all.begin(), all.end()), all.end());
	printf("%s\n", all[k - 1].c_str());
	
	
	return 0;
}


Measured memory_bytes: 4392
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;
int n;


int solve(vector<int> &v, int cur){
    if(cur >= n) return 0;
    if(v[cur] == 0) return solve(v, cur+1);
    int ans = n;
    int w = v[cur];
    for (int i = cur; i < n; ++i) {
        v[i] = (v[i]+10-w)%10;
        ans = min(ans, solve(v, cur+1)+1);
    }
    for (int i = cur; i < n; ++i) {
        v[i] = (v[i]+w)%10;
    }
    return ans;
}

int main() {
    while(cin >> n, n){
        string s, t;
        cin >> s >> t;
        vector<int> v(n);
        for (int i = 0; i < n; ++i) {
            v[i] = (s[i]-t[i]+10)%10;
        }
        cout << solve(v, 0) << "\n";
    }
    return 0;
}


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

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

typedef long long ll;
typedef long long int64;

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

  string s;
  cin >> s;

  if(s[k-1] == 'A'){
    s[k-1] = 'a';
  }
  else if(s[k-1] == 'B'){
    s[k-1] = 'b';
  }
  else if(s[k-1] == 'C'){
    s[k-1] = 'c';
  }

  cout << s << endl;

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int main()
{
    int a,b,tmp=1;
    scanf("%d %d",&a,&b);
    while(tmp<=b)
        tmp*=10;
    a=a*tmp+b;
    double ans=sqrt((double)a);
    if((int) ans==ans)
        printf("Yes");
    else
        printf("No");
}


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

#define pb push_back
#define mp make_pair

#define fi first
#define se second

typedef long long ll;

using namespace std;
int n, cost;
int a[5005], b[5005][5005];

int main(){

cin >> n >> cost;
for(int i = 0; i < n; i++) {
    cin >> a[i];
    a[i + n] = a[i];
}
for(int i = 0; i < n + n; i++) {
    b[i][i] = a[i];
    for(int j = i + 1; j < n + n; j++) {
        b[i][j] = min(b[i][j - 1], a[j]);
    }
}
ll ans = 1e15;
for(int m = 0; m < n; m++) {
    ll res = m * 1ll * cost;
    for(int i = 0; i < n; i++){
        res += b[i][i + m];
    }
    ans = min(ans, res);
}
cout << ans;
return 0;
}


Measured memory_bytes: 80128
#include <iostream>
#include <string>
#include <deque>

using namespace std;

int main()
{
	deque<int> D;
	
	int q;
	cin >> q;
	
	for (int i = 0; i < q; i++)
	{
		int cmd, d, x, p;
		cin >> cmd;
		switch (cmd)
		{
			case 0:
				cin >> d >> x;
				if (d)
					D.push_back(x);
				else
					D.push_front(x);
				break;
			case 1:
				cin >> p;
				cout << D[p] << endl;
				break;
			case 2:
				cin >> d;
				if (d)
					D.pop_back();
				else
					D.pop_front();
				break;				
		}
	}
}


Measured memory_bytes: 4632
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<ll> vll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define Sort(a) sort(a.begin(), a.end())
#define fin(ans) cout << (ans) << endl
const int INF = 1<<30;
const ll MOD = 1000000007;

int main() {
    long long K,N,min=INF,sum=0,m=0;
    int a=1;
    cin >> K >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A.at(i);
    }
    m=A.at(0)+K-A.at(N-1);
    for (int i = 0; i < N-1; i++) {
        m=max(A.at(i+1)-A.at(i),m);
    }

    cout << K-m << endl;
}

Measured memory_bytes: 1792
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <functional>

using namespace std;

#define fst first
#define scd second
#define PB push_back
#define MP make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define omajinai ios::sync_with_stdio(false);cin.tie(0)
#define rep(i,x) for(int i=0;i<(int)(x);++i)
#define rep1(i,x) for(int i=1;i<=(int)(x);++i)
#define rrep(i,x) for(int i=(int)x-1;i>=0;--i)
#define rrep1(i,x) for(int i=(int)x;i>=1;--i)

using ll=long long;
using ld=long double;
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int, int>;
using vpii=vector<pii>;

template<class T,class U>ostream&operator<<(ostream&os,const pair<T,U>p){os<<"("<<p.fst<<", "<<p.scd<<")";return os;}
template<class T>ostream&operator<<(ostream&os,const vector<T>v){rep(i,v.size()){if(i)os<<", ";os<<v[i];}return os;}
template<typename T>T&max(T&a,T&b){if(a>=b)return a;return b;}
template<typename T>T&min(T&a,T&b){if(a < b)return a;return b;}
template<typename T>bool chmax(T&a,T b){if(a < b){a=b;return true;}return false;}
template<typename T>bool chmin(T&a,T b){if(a > b){a=b;return true;}return false;}

constexpr int inf = 1e9;
constexpr ll linf = 3e18;
constexpr double eps = 1e-9;

int m, n;
int a[92][92];
int ma = 0;

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

bool inside(int y, int x)
{
    return 0 <= y && y < n && 0 <= x && x < m;
}

void dfs(int y, int x, int n)
{
    chmax(ma, n);

    rep(i, 4) {
        int ny = y + dy[i], nx = x + dx[i];

        if (inside(ny, nx) && a[ny][nx]) {
            a[ny][nx] = 0;
            dfs(ny, nx, n + 1);
            a[ny][nx] = 1;
        }
    }
}

signed main()
{
    while (cin >> m >> n, m) {
        ma = 0;
        memset(a, 0, sizeof a);
        rep(i, n) rep(j, m) cin >> a[i][j];

        rep(i, n) rep(j, m) {
            if (a[i][j]) {
                a[i][j] = 0;
                dfs(i, j, 1);
                a[i][j] = 1;
            }
        }

        cout << ma << endl;
    }
}

Measured memory_bytes: 3056
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <tuple>
#include <queue>
#include <bitset>
#include <set>
#include <map>
#include <list>

using namespace std;


void solve(long long H, long long A){
  std::cout << (H-1)/A + 1 << std::endl;
}

int main(){
  long long H;
  scanf("%lld",&H);
  long long A;
  scanf("%lld",&A);
  solve(H, A);
  return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<iomanip>
#include<queue>
#include<stack>
#include<time.h>
#define rep(i,n)for(ll i=0;i<n;i++)
#define ll long long
#define ggr getchar();getchar();return 0;
#define prique priority_queue
#define inf 1145141919364364
#define double long double
using namespace std;
typedef pair<ll, ll>P;
ll gcd(ll x, ll y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
ll lcm(ll x, ll y) {
	return x * y / gcd(x, y);
}
signed main() {
	ll a, b, c;
	cin >> a >> b >> c;
	cout << a + b + c - max({ a,b,c }) << endl;
	ggr
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define F first
#define S second

using namespace std;
typedef pair<int,int> P;

const int MOD=1000000007;
int INF=100100100100100;

vector<pair<char,int>> RL_S(string s){
  vector<pair<char,int>> res;
  int n=s.length();
  char ima;int cnt=0;
  rep(i,n){
    if(cnt==0){
      ima=s[i];
      cnt++;
    }
    else if(s[i]==ima)cnt++;
    else{
      res.pb(make_pair(ima,cnt));
      ima=s[i];
      cnt=1;
    }
  }
  res.pb(make_pair(ima,cnt));
  return res;
}

int a[100010];
signed main(){
  string s;cin>>s;
  int k;cin>>k;
  int ans=0;
  vector<pair<char,int>> v=RL_S(s);
  int n=v.size();
  
  if(n==1){
    cout<<(s.length()*k)/2<<endl;
    return 0;
  }
  
  int m1=v[0].S,m2=v[n-1].S;
  if(v[0].F==v[n-1].F)ans+=((k-1)*((m1+m2)/2)+m1/2+m2/2);
  else ans+=k*((m1/2)+(m2/2));
  
  for(int i=1;i<n-1;i++){
    int l=v[i].S;
    ans+=k*(l/2);
  }
  cout<<ans<<endl;  
  return 0;
}

Measured memory_bytes: 3592
#include <cctype>
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); ++i)

map<char, int> val;
string in;
int p;

int formula(){
    int res = -1;
    if(isdigit(in[p]))res = in[p++] - '0';
    else if(isalpha(in[p]))res = val[in[p++]];
    else if(in[p] == '-'){
        p++;
        res = 2 - formula();
    }
    else if(in[p] == '('){
        p++;
        int x = formula();
        bool plus = in[p++] == '+';
        int y = formula();
        p++;
        res = plus? max(x, y): min(x, y);
    }
    return res;
}

int main(){
    while(cin >> in, in != "."){
        int ans = 0;
        rep(i, 3){
            val['P'] = i;
            rep(j, 3){
                val['Q'] = j;
                rep(k, 3){
                    val['R'] = k;
                    p = 0;
                    ans += 2 == formula();
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

Measured memory_bytes: 1192
// Heap ii
#include <stdio.h>
#include <stdlib.h>

typedef struct node {
  int key;
  struct node* parent;
  struct node* left;
  struct node* right;
} node_p;

void maxHeapify(node_p*, int);
void buildMaxHeap(node_p*);

int n;

int main() {
  int i;
  node_p* node;

  // input
  scanf("%d", &n);

  // memory allocate
  node = (node_p*)malloc((n+1) * sizeof(node_p));

  // input the key of node
  for(i = 1; i <= n; i++) {
    scanf("%d", &node[i].key);
    if(i == 1) {
      node[i].parent = NULL;
    }
    else {
      if(i % 2 == 0) node[i/2].left = &node[i];
      else node[i/2].right = &node[i/2];
      node[i].parent = &node[i/2];
    }
    node[i].left = NULL;
    node[i].right = NULL;
  }

  buildMaxHeap(node);

  for(i = 1; i <= n; i++) {
    printf(" %d", node[i].key);
  }
  printf("\n");

  return 0;
}

void maxHeapify(node_p* node, int i) {
  int l, r, largest;
  node_p tmp;

  l = 2*i;
  r = 2*i+1;
  // choose the node which has max value
  if((l <= n) && (node[l].key > node[i].key)) {
    largest = l;
  } else {
    largest = i;
  }
  if((r <= n)&&(node[r].key > node[largest].key)) {
    largest = r;
  }
  if(largest != i){ // child of i is bigger than i
    // exchange
    tmp = node[i];
    node[i] = node[largest];
    node[largest] = tmp;
    // recursive
    maxHeapify(node, largest);
  }
}

void buildMaxHeap(node_p *node) {
  int i;
  
  for(i = n/2; i >= 1; i--) {
    maxHeapify(node, i);
  }
}



Measured memory_bytes: 17336
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
#define MOD 1000000007
typedef long long ll;

using namespace std;

int main() 
{
  string w;
  cin >> w;
  string s;
  int cnt = 0;

  while (cin >> s) {
    if (s == "END_OF_TEXT") break;
    transform(s.begin(), s.end(), s.begin(), ::tolower);

    if (w == s) cnt++;
  }

  cout << cnt << "\n";
}



Measured memory_bytes: 3172
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
//#include <atcoder/all>
//using namespace atcoder;
using namespace std;
#define all(v) v.begin(), v.end()
using in = int64_t;
#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 Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
const double PI=3.14159265358979323846;
const in MOD =998244353;
const in INF=1e18+7;
const int inf=1e9+7;
using P=pair<int,int>;
vector<int> dx={0,1,-1,0};
vector<int> dy={1,0,0,-1};


//探索、更新にO(log n)
struct segment_tree{
    int init ; //　空いてる値はこれになる
    int n; //　n個のデータ
    vector<int> data; // データ置き場・n-1~2n-1に元データ

    //(個数、初期値)
    //初期化　nを2の累乗に直す  初期値は最も選ばれない値にする
    segment_tree(int a, int b) : init(b) {
        n = 1;
        while( n < a ) n *= 2;
        data.assign(n * 2 - 1,init);
    }

    //+とかにしてもいい、結合法則はいる
    //選ぶ方の決め方（ここでは小さい方）
    int which(int a, int b){
        return (a+b)%MOD;
    }

    // k番目をaに更新
    void update(int k, int a){
        k += n-1;
        data[k] = a;

        //下から上に更新
        while( k > 0 ){
            k = (k - 1) / 2;
            data[k] = which( data[k*2+1] , data[k*2+2] );
        }
    }

    // [a, b)の最小値を求める
    // 後ろのほうの引数は、計算の簡単のための引数。
    // kは節点の番号、l, rはその節点が[l, r)に対応づいていることを表す。
    // したがって、外からはquery(a, b, 0, 0, n)として呼ぶ。
    int query( int a, int b, int k, int l, int r){

        // [a, b)と[l, r)が交差しなければ、MAX_INT
        if(r <= a || b <= l) return init;

        // [a, b)が[l, r)を完全に含んでいれば、この節点の値
        if(a <= l && r <= b) return data[k];

        // そうでなければ、2つの子の最小値
        int vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
        int vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
        return which( vl, vr );
    }

    // 外から呼ぶとき用
    // [a, b)の最小値を求める
    int query( int a, int b){
        return query( a, b, 0, 0, n);
    }

    // a番目のデータを見る
    // query(a,a+1)で良くね？
    int look(int a){
        return data[a+n-1];
    }
};

int main(){
ios::sync_with_stdio(false);cin.tie(nullptr);
cout << fixed << setprecision(10);
    vector<P> a(0);
    vector<int> dp(0);
    int n,k;
    cin>>n>>k;
    vector<int> L(k),R(k);
    rep(i,k) cin>>L[i]>>R[i];
    
    rep(i,k) a.emplace_back(L[i],R[i]);
    sort(all(a));
    dp.resize(n,-1);

    segment_tree sg(n,0);
    sg.update(0,1);
    REP(i,1,n){
        int cnt=0;
        rep(j,k){
            if(i-L[j]<0) continue;
            if(i-R[j]<0) cnt += sg.query(0,i-L[j]+1);
            else cnt += sg.query(i-R[j],i-L[j]+1);
            cnt %=MOD;
        }
        sg.update(i,cnt);
    }
    cout<<sg.look(n-1)<<endl;
}/*
./problem.exe
*/

Measured memory_bytes: 6120
// https://atcoder.jp/contests/abc066/tasks/abc066_c
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define REP(i, n) FOR(i, 0, n)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> v(n);
    REP(i, n) cin >> v[i];
    deque<int> q;
    REP(i, n) {
        if (i % 2 == 0) {
            q.push_back(v[i]);
        } else {
            q.push_front(v[i]);
        }
    }
    if (n % 2 == 1) {
        reverse(ALL(q));
    }
    for (auto &x : q) {
        cout << x << " ";
    }
    cout << "\n";

    return 0;
}


Measured memory_bytes: 3840
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for(ll i=0; i<(ll)n; i++)
#define REPR(i, n) for(ll i=(ll)n-1; i>=0; i--)
#define FOR(i, m, n) for(ll i=(ll)m; i<(ll)n; i++)
#define FORR(i, m, n) for(ll i=(ll)m-1; i>=(ll)n; i--)
#define ALL(x) (x).begin(), (x).end()
#define ASC(v) sort(ALL(v));
#define DESC(v) sort(ALL(v), greater<int>());
#define UNIQ(a) sort(ALL(a));(a).resize(unique(ALL(a)) - a.begin());
#define PRINTD(x, d) cout << fixed << setprecision(d) << x << "\n";
#define DEBUG(x) cout<<#x<<": "<<x<<"\n"
const double PI = acos(-1);
ll lcm(ll a, ll b) { return a / __gcd(a, b) * b; }
bool isprime(int x){ int i; if(x<2)return 0; else if(x==2) return 1; if(x%2==0) return 0; for(i=3; i*i<=x; i+=2) if(x%i==0) return 0; return 1; }
int digsum(int n) { int r=0; while(n>0) { r+=n%10; n/=10; } return r; }
vector<string> split(string s, char p){vector<string>v;stringstream m(s);string b;while(getline(m,b,p))v.push_back(b);return v;}
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 (a>b) { a = b; return 1; } return 0; }
struct nya{ nya(){ cin.tie(0); ios::sync_with_stdio(false); } }nyan;

int main(){
    ll N; cin >> N;
    ll pre; cin >> pre;
    ll ans = 0;
    FOR(n, 1, N) {
        ll A; cin >> A;
        if (pre > A) ans += pre-A;
        else pre = A;
    }
    cout << ans << "\n";
}


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

#define rep(i, m, n) for(int(i) = (int)(m); i < (int)(n); ++i)
#define rep2(i, m, n) for(int(i) = (int)(n)-1; i >= (int)(m); --i)
#define REP(i, n) rep(i, 0, n)
#define REP2(i, n) rep2(i, 0, n)
#define all(hoge) (hoge).begin(), (hoge).end()
#define en '\n'
using ll = long long;
using ull = unsigned long long;
template <class T>
using vec = vector<T>;
template <class T>
using vvec = vector<vec<T>>;
typedef pair<ll, ll> P;
using tp = tuple<ll, ll, ll>;
constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
//constexpr long long MOD = (ll)1e9 + 7;
constexpr long long MOD = 998244353LL;
using ld = long double;
static const ld pi = 3.141592653589793L;
typedef vector<ll> Array;
typedef vector<Array> Matrix;

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

//グラフ関連
struct Edge {
    ll to, cap, rev;
    Edge(ll _to, ll _cap, ll _rev) {
        to = _to;
        cap = _cap;
        rev = _rev;
    }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void add_edge(Graph &G, ll from, ll to, ll cap, bool revFlag, ll revCap) {
    G[from].push_back(Edge(to, cap, (ll)G[to].size()));
    if(revFlag)
        G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}

void solve() {
    ll n;
    cin >> n;
    vec<ll> a(n), b(n), c(n + 1, 0), d(n + 1, 0);
    REP(i, n) {
        cin >> a[i];
        c[a[i]]++;
    }
    REP(i, n) {
        cin >> b[i];
        d[b[i]]++;
    }
    REP(i, n) {
        if(c[i + 1] + d[i + 1] >= n + 1) {
            cout << "No" << en;
            return;
        }
        c[i + 1] += c[i];
        d[i + 1] += d[i];
    }

    ll x = -INF;
    rep(i, 1, n + 1) {
        chmax(x, c[i] - d[i - 1]);
    }

    cout << "Yes" << en;
    vec<ll> ans(n);
    REP(i, n) {
        ans[(i + x) % n] = b[i];
    }
    for(auto i : ans)
        cout << i << " ";
    cout << en;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    /*
    ll t;
    cin >> t;
    while(t--)*/
    solve();

    return 0;
}


Measured memory_bytes: 11188
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<functional>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

int N, M, C;
vector<vector<P>> edge;
ll ans = 222222222222;
ll edgect = 0;

void djk() {
	ll d[100000];
	bool memo[100000] = {};
	for (int i = 0; i < N; i++)d[i] = 100000000007;
	d[0] = 0;
	memo[0] = true;
	priority_queue<P, vector<P>, greater<P>> pq;
	pq.push(P(0, 0));
	while (pq.size()) {
		auto tmp = pq.top(); pq.pop();
		memo[tmp.second] = true;

		if (tmp.first > d[tmp.second])continue;
		
		//cout << d[1] << endl;

		for (int i = 0; i < edge[tmp.second].size(); i++) {
			auto to = edge[tmp.second][i];
			if (memo[to.first]) {
				edgect -= to.second;
			}
		}

		ans = min(ans, d[tmp.second] * C + edgect);

		for (int i = 0; i < edge[tmp.second].size(); i++) {
			auto to = edge[tmp.second][i];
			if (d[to.first] > d[tmp.second] + to.second) {
				d[to.first] = d[tmp.second] + to.second;
				pq.push(P(d[to.first], to.first));
			}
		}

	}
}

int main() {
	cin >> N >> M >> C;
	edge.resize(N);
	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		a--, b--;
		edge[a].push_back(P(b, c));
		edge[b].push_back(P(a, c));
		edgect += c;
	}
	
	djk();
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 12868
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
x = N * 800
y = N // 15 * 200
print(x - y)

Measured memory_bytes: 3892