akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>

/*
void insertionSort(int a[], int n) {
	int i;
	int v;
	int j;
	int k;
	for (i = 1; i<n; i++) {
		v = a[i];
		j = i - 1;
		while (j >= 0 && a[j]>v) {
			a[j + 1] = a[j];
			j--;
			a[j + 1] = v;
	
		}
		for (k = 0; k<n; k++) {

			printf("%d ", a[k]);

		}
		printf("\b\n");
	}


}*/

int main(void)
{
	int a[1001];
	int n;
	int i;
	int k;
	int v;
	int j;
	scanf("%d", &n);
	for (i = 0; i<n; i++) {

		scanf("%d", &a[i]);

	}
	for(i=0;i<n;i++){ printf("%d",a[i]); if(i!=n-1) printf(" ");}
	printf("\n");
	for (i = 1; i<n; i++) {
		v = a[i];
		j = i - 1;
		while (j >= 0 && a[j]>v) {
			a[j + 1] = a[j];
			j--;
			a[j + 1] = v;

		}
		for (k = 0; k<n; k++) {

			printf("%d", a[k]);
			if(k!=n-1) printf(" ");

		}
			
			printf("\n");
	}


	return 0;
}




Measured memory_bytes: 2040
def dis(a,b):
  ans = 0
  sum = 0
  
  for i in range(d):
   # print("a is",a[i])
   # print("b is",b[i])
    sum += (a[i] - b[i]) ** 2
   
  ans = sum ** 0.5
  return ans

n, d = map(int, input().split())
x = [list(map(int, input().split())) for i in range(n)]
#print(x)
count = 0

for i in range(0, n-1):
  for j in range(i+1, n):
 #   print(x[i])
 #   print(x[j])
    if dis(x[i], x[j]).is_integer():
      count += 1
    
print(count)


Measured memory_bytes: 3064
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W, K = [int(x) for x in input().split()]
    X1, Y1, X2, Y2 = [int(x) for x in input().split()]
    C = [input().strip() for _ in range(H)]

    q = collections.deque()
    q.append((X1 - 1, Y1 - 1, 0))

    V = [[float("inf")] * W for j in range(H)]
    V[X1 - 1][Y1 - 1] = 0


    while q:
        c = q.popleft()
        x = c[0]
        y = c[1]
        d = c[2]

        if y == Y2 - 1 and x == X2 - 1:
            print(c[2])
            return

        e, w, n, s = True, True, True, True
        for k in range(1, K + 1):
            if not e and not w and not n and not s:
                break
            if e:
                if y + k >= W or C[x][y + k] == "@":
                    e = False
                else:
                    if V[x][y + k] == float("inf"):
                        V[x][y + k] = d + 1
                        q.append((x, y + k, d + 1))

                    if V[x][y + k] < d + 1:
                        e = False
            if w:
                if y - k < 0 or C[x][y - k] == "@":
                    w = False
                else:
                    if V[x][y - k] == float("inf"):
                        V[x][y - k] = d + 1
                        q.append((x, y - k, d + 1))
                    if V[x][y - k] < d + 1:
                        w = False

            if n:
                if x - k < 0 or C[x - k][y] == "@":
                    n = False
                else:
                    if V[x - k][y] == float("inf"):
                        V[x - k][y] = d + 1
                        q.append((x - k, y, d + 1))
                    if V[x - k][y] < d + 1:
                        n = False

            if s:
                if x + k >= H or C[x + k][y] == "@":
                    s = False
                else:
                    if V[x + k][y] == float("inf"):
                        V[x + k][y] = d + 1
                        q.append((x + k, y, d + 1))
                    if V[x + k][y] < d + 1:
                        s = False

    print(-1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 36788
import java.util.Scanner;

public class Main
{
    public static void main( String[] args )
    {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        if(N%2 == 0){
            System.out.println(N/2);
        }else{
            System.out.println(N/2 + 1);
        }
        scanner.close();
    }
}

Measured memory_bytes: 22868
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define pll  pair <long long,long long>
#define ss second
#define ff first
#define inf 9223372036854775807
#define maa 1000000007
#define ld long double
#define fast  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define bug(x) cout << #x <<": " << x << '\n';
const ll N=200001 ;
int main()
{
   fast ;
   ll k ;
   cin>>k  ;
   string s="1" ;

   for(ll l=2;l<=k;l++)
   {
       ll n=s.length() ;
       ll in=-1 ;
       for(ll i=n-1;i>0;i--)
       {
           ll x=s[i-1]-'0',y=s[i]-'0' ;
           if(y==x-1)
           {
               s[i]=s[i-1] ;
               in=i ;
               break ;
           }
           else if(y==x&&x!=9)
           {
               s[i]=(s[i-1]+1) ;
               in=i ;
               break ;
           }
       }
       if(s[0]!='9'&&in==-1)
       {
           s[0]=(s[0]+1) ;
           in=0 ;
       }
       if(in!=-1)
       {
           for(ll j=in+1;j<n;j++)
           {
               if(s[j-1]!='0')
               {
                   s[j]=(s[j-1]-1) ;
               }
               else
               {
                   s[j]=s[j-1] ;
               }
           }
       }
       if(in==-1)
       {
           s="1" ;
           for(ll i=0;i<n;i++)s+='0' ;

       }

       //cout<<l<<" "<<s<<endl ;
   }

   cout<<s ;


}



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


int N;
int C;

int A[404];
int B[404];
int X[400];

ll MOD = 1000000007;

// (i, j) => pow(i, j) or i ^ j 
ll ppow[404][404];

// (i, 0) => 0
// (i, j) => i^0 + i^1 + ... + i^(j-1)
ll ppows[404][404];

ll ans;

// (N, C)
ll dp[404][404];


int main(int argc, char* argv[]) {
    // for cin
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> N >> C;

    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    
    for (int i = 0; i < N; ++i) {
        cin >> B[i];
    }

    ppow[0][0] = 1;

    for (int i = 1; i <= 400; i++) {
        ppow[i][0] = 1;
        for (int j = 0; j < 400; ++j) {
            (ppow[i][j+1] = ppow[i][j] * i) %= MOD;
        }
    }

    for (int i = 0; i < 401; ++i) {
        for (int j = 0; j < 401; ++j) {
            (ppows[j+1][i] = ppows[j][i] + ppow[j][i]) %= MOD;
        }
    }
 
    dp[0][0] = 1;

    for (int i = 0; i < N; ++i) {
        for (int x = 0; x < C+1; ++x) {
            for (int y = 0; x+y <= C; y++) {
                ll p = (ppows[B[i]+1][y] - ppows[A[i]][y]) % MOD;

                if (p < 0) {
                    p += MOD;
                }

                (dp[i+1][x+y] += dp[i][x] * p) %= MOD;
            }
        }
    }
    cout << dp[N][C] << endl;

    //for (int i = 0; i < 5; ++i) {
    //    for (int j = 0; j < 7; ++j) {
    //        cout << ppow[i][j] << " ";
    //    }
    //    cout << endl;
    //}
    //cout << endl;

    //for (int i = 0; i < 5; ++i) {
    //    for (int j = 0; j < 7; ++j) {
    //        cout << ppows[i][j] << " ";
    //    }
    //    cout << endl;
    //}

    //for (int i = 0; i < N+1; ++i) {
    //    for (int x = 0; x < C+1; ++x) {
    //        cout << dp[i][x] << " ";
    //    }
    //    cout << endl;
    //}

    return 0;
}


Measured memory_bytes: 4096
#include<iostream>
#include<string>
#include<vector>
#include<numeric>
#include<math.h>
#include<algorithm>
#include<iomanip>
#include<list>
#include<bitset>
using namespace std;

int main() {

	int D;
	cin >> D;

	vector<int> c(26, 0);
	for (int i = 0; i < c.size(); i++) {
		cin >> c[i];
	}

	vector<vector<int>> s(D, vector<int>(26, 0));
	for (int i = 0; i < s.size(); i++) {
		for (int j = 0; j < s[i].size(); j++) {
			cin >> s[i][j];
		}
	}

	vector<int> t(D, 0);
	for (int i = 0; i < t.size(); i++) {
		cin >> t[i];
		t[i]--;
	}

	int ans = 0;

	vector<int> last(26, -1);

	for (int i = 0; i < t.size(); i++) {
		ans += s[i][t[i]];
		last[t[i]] = i;
		for (int j = 0; j < c.size(); j++) {
			ans -= c[j] * (i - last[j]);
		}
		cout << ans << endl;
	}

	return 0;
}

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

int max( int a, int b )
{
    if( a > b )
        return a;
    else
        return b;
}

int days( int a, int b )
{
    if( a % b != 0 )
        return a / b + 1;
    else
        return a / b;
}

int main()
{
    int l, a, b, c, d, m, n;

    cin >> l >> a >> b >> c >> d;

    cout << l - max( days( a, c ), days( b, d ) ) << endl;

    return 0;
}


Measured memory_bytes: 3104
#include<stdio.h>
int main(void){
int n[4];
  for(int i=0;i<3;i++){
	scanf("%d",&n[i]);
  }
  int c=0;
  for(int i=0;i<2;i++){
	for(int j=i+1;j<3;j++){
      if(n[i]==n[j])c++;
    }
  }
  if(c==1)printf("Yes");
  else printf("No");
  return 0;
}

Measured memory_bytes: 128
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
using namespace std;
//typedef __int64 LL;
//typedef long long int LL;
typedef vector<int> ivec;
typedef vector<string> svec;
typedef pair<int,int> P;
//typedef pair<LL,LL> PL;

const int MOD=1000000007;

int main(){
	int n;cin>>n;
	string s;cin>>s;
	if(n%2!=0)
	{
		cout<<"No"<<"\n";
		return 0;
	}
	
	int m=n/2;
	for(int i=0;i<m;i++)
	{
		if(s[i]!=s[i+m])
		{
		cout<<"No"<<"\n";
		return 0;	
		}
	}
	cout<<"Yes"<<"\n";
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
         Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        int c = a * b;

        if(c % 2 == 0){
            System.out.println("Even");
        }else{
            System.out.println("Odd");
        }
        scanner.close();
    }
}

Measured memory_bytes: 35668
#include <bits/stdc++.h>
using namespace std;
 
 int findsum(int n){    //格桁の総和を計算する関数
     int sum = 0;
     while(n>0){
          sum += n % 10;
          n /= 10;
      }
      return sum;
  }
 
int main() {
    int N, A, B;
    int total=0;
    int count=0;
    
    cin >> N >> A >> B;
    
    for(int i=1; i<=N; i++){
        total = findsum(i);
    
    	if(total >= A && total <= B){
        	count += i;   
    	}
    }
  
    cout << count << endl;      //合計出力
    
    return 0;
}

Measured memory_bytes: 256
module WeightedDirectedGraph
  (Weight : sig
    type t
    val inf : t (* オーバーフローの恐れはないので，max_intとか突っ込んでも良い *)
    val zero : t
    val neg_inf : t (* オーバーフローの恐れはないので，min_intとか突っ込んでも良い *)
    val ( + ) : t -> t -> t
    val compare : t -> t -> int
  end) :
sig
  type 'a church_list = { fold : 'b. ('a -> 'b -> 'b) -> 'b -> 'b }

  val bellman_ford :
    (* 頂点数n *)
    int ->
    (* 辺のリスト
       頂点は0からn-1までの整数でなくてはならない *)
    (int * int * Weight.t) church_list ->
    (* 始点 *)
    int ->
    (* 頂点を受け取り，そこまでの距離を返す関数
       頂点に到達するパスが無ければinfを返し，
       そこに到達するまでに負閉路があればneg_infを返す *)
    (int -> Weight.t)
end =
struct
  type 'a church_list = { fold : 'b. ('a -> 'b -> 'b) -> 'b -> 'b }

  let bellman_ford n es s =
    (* 距離を覚えるやつ *)
    let d = Array.make n Weight.inf in
    (* 始点より終点のインデックスが大きくなる辺を集めた隣接リスト *)
    let inc = Array.make n [] in
    (* 始点より終点のインデックスが小さくなる辺を集めた隣接リスト *)
    let dec = Array.make n [] in
    es.fold (fun ((u, v, _) as e) () ->
      if u <= v
      then inc.(u) <- e :: inc.(u)
      else dec.(u) <- e :: dec.(u)) ();
    d.(s) <- Weight.zero;
    (* n / 2 回目以降の各辺の処理 *)
    let f is_modified (u, v, c) =
      (* 原点から到達できない頂点は更新しない *)
      if 0 <= Weight.compare d.(u) Weight.inf
      then is_modified
      else
        let dv =
          if 0 <= Weight.compare Weight.neg_inf d.(u)
          then Weight.neg_inf
          else let open Weight in d.(u) + c in
        if 0 <= Weight.compare dv d.(v)
        then is_modified
        else (d.(v) <- Weight.neg_inf; true) in
    (* n / 2 回以降の反復 *)
    let rec iter' = function
      | 0 -> ()
      | i ->
          if
            Array.fold_right (Fun.flip (List.fold_left f)) dec @@
            Array.fold_left (List.fold_left f) false inc
          then iter' (i - 1) in
    (* n / 2 回目以前の各辺の処理 *)
    let f is_modified (u, v, c) =
      (* 原点から到達できない頂点は更新しない *)
      if 0 <= Weight.compare d.(u) Weight.inf
      then is_modified
      else
        let dv = let open Weight in d.(u) + c in
        if 0 <= Weight.compare dv d.(v)
        then is_modified
        else (d.(v) <- dv; true) in
    let rec iter = function
      | 0 -> iter' (succ n lsr 1)
      | i ->
          if
            Array.fold_right (Fun.flip (List.fold_left f)) dec @@
            Array.fold_left (List.fold_left f) false inc
          then iter (i - 1) in
    iter (n lsr 1);
    Array.get d
end

module G = WeightedDirectedGraph (struct
  type t = int
  let zero = 0
  let inf = min_int
  let neg_inf = max_int
  let ( + ) = ( + )
  let compare x y = compare y x
end)

let () = Scanf.scanf "%d %d %d\n" @@ fun n m p ->
  let abc = Array.init m @@ fun _ ->
    Scanf.scanf "%d %d %d\n" @@ fun a b c -> a - 1, b - 1, c - p in
  let d = G.bellman_ford n { G.fold = fun f -> Array.fold_right f abc } 0 (n - 1) in
  if max_int <= d
  then print_endline "-1"
  else Printf.printf "%d\n" @@ max 0 d


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

int main(){
        int a,b,c;
        int ans1=0,ans2;
        cin >> a >> b;
        c = b-a;
        for(int i=1; i<=c; i++) {
                ans1 += i;
        }
        ans2 = ans1-b;
        cout << ans2 << endl;


        return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#define N (int)1e6
using namespace std;

int main(){
  int n,tmp,dp[N],dp_odd[N];
  int plc[1000],num;

  for(int i=0;i<N;i++)dp[i] = dp_odd[i] = N+1;
  dp[0] = dp_odd[0] = 0;

  tmp = 1;
  for(num=1;;num++){
    plc[num] = tmp;
    tmp *= num+3; tmp /= num;
    if(tmp>=N)break;
  }
  
  for(int i=0;i<N;i++){
    for(int j=1;j<num;j++){
      if(i<plc[j])break;
      dp[i] = min(dp[i],dp[i-plc[j]]+1);
      if(plc[j]&1)dp_odd[i] = min(dp_odd[i],dp_odd[i-plc[j]]+1);
    }
  }

  while(scanf("%d",&n) && n)printf("%d %d\n",dp[n],dp_odd[n]);
}

Measured memory_bytes: 8452
#include<stdio.h>

int main(void){
  char s[100001];
  scanf("%s",s);

  int count = 0;
  for(int i = 0;s[i+1] != '\0';i ++){
    if(s[i] != s[i+1]){
      count ++;
    }
  }

  printf("%d\n",count);

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define mk make_pair
#define all(a) a.begin(), a.end()
#define len(a) (int)a.size()

using namespace std;

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

void solve(){
	int x, y;
	cin >> x >> y;
	if(4 * x >= y && (4*x - y) % 2 == 0){
		int a = (4 * x - y) / 2;
		int b = x - a;
		if(b < 0)
			cout << "No" << endl;
		else{
			if(a * 2 + b * 4 == y)
				cout << "Yes" << endl;
			else
				cout << "No" << endl;
		}
	}
	else
		cout << "No" << endl;
}

int main(){
	solve();
	return 0;
}


Measured memory_bytes: 3612
while True:
  m, f, r = map(int, input().split())
  if m == f == r == -1: break
  if m == -1 or f == -1:
    print("F")
  elif m+f >= 80:
    print("A")
  elif m+f >= 65:
    print("B")
  elif m+f >= 50 or r >= 50:
    print("C")
  elif m+f >= 30:
    print("D")
  else:
    print("F")


Measured memory_bytes: 5596
import java.util.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int H = sc.nextInt();
		int ans = 1;
		
		for (int i=1; i<N; i++) {
			int a = sc.nextInt();
			if (H >= a) {
				ans++;
			}
			H = Math.min(a,H);
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 63996
function main() {
	input = input[0].split(' ');
	
	height = input[0];
	width  = input[1];

	S = height * width;
	A = 2 * height + 2 * width;

	console.log(S + ' ' + A);
}

var input = "";

process.stdin.resume();
process.stdin.setEncoding("utf-8");
process.stdin.on("data", function(chunk) {
	input += chunk;
});

process.stdin.on("end", function() {
	input = input.split("\n");
	main();
})

Measured memory_bytes: 15540
l,r = map(int, input().split())
if (r-l >= 2018):
    print(0)
    exit()
a = []
for i in range(l,r+1):
    a.append(i%2019)
a.sort()
if (a[0]==0):
    print(0)
    exit()
b = []
for i in range (0,len(a)-1):
    for j in range (1,len(a)):
        b.append((a[i]*a[j])%2019)
print(min(b))
    

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

int cnt(int n){
  int ret = 0;
  int i = 1;
  while(i*i < n){
    if(n%i == 0) ret += 2;
    i++;
  }
  return ret;
}

int main() {
  int N, ans;
  cin >> N;
  ans = 0;
  rep(i, N+1){
    if(i % 2 == 0) continue;
    if(cnt(i) == 8) ans += 1;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
T = int(input())

for _ in range(T):
    N = int(input())
    A = list(map(int,input().split()))
    S = input()

    if S[-1] == '1':
        print(1)
        continue

    list0 = [0] * 64

    for a, s in zip(reversed(A), reversed(S)):
        blen = a.bit_length()
        for i in range(blen, 0, -1):
            if a.bit_length() < i: continue
            if list0[i - 1]:
                a ^= list0[i - 1]
                if a == 0: break

        else:
            if s == '1':
                ans = 1
                break
            else:
                list0[a.bit_length() - 1] = a

    else:
        ans = 0

    print(ans)


Measured memory_bytes: 9052
h, w, k = map(int, input().split())
c = [input() for i in range(h)]

kazu = 0

for i in range(2 ** w):
    for s in range(2 ** h):
        count = 0
        for j in range(w):
            if ((i >> j) & 1):
                for t in range(h):
                    if ((s >> t) & 1):
                        if c[t][j] == '#':
                            count += 1
            
        if count == k:
            kazu += 1

print(kazu)

Measured memory_bytes: 9080
#include <bits/stdc++.h>
using namespace std;
#define PI 3.14159265358979323
#define ll long long int
#define vi vector <int>
#define vl vector <ll>
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define watch(x) cout << (#x) << " is " << (x) << "\n"
#define MOD 1000000007
ll power(ll a, ll b) { //a^b
	ll res = 1;
	while (b > 0) {
		if (b & 1) {res = (res * a); b--;}
		a = (a * a);
		b >>= 1;
	}
	return res;
}
ll n;
ll gcd(ll a, ll b) {return (b == 0) ? a : gcd(b, a % b);}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	ll ww;
	cin>>n>>ww;
	vl v(n),w(n);
	for(ll i=0;i<n;i++)
		cin>>w[i]>>v[i];
	vector < vector <ll> > dp (n+1,vector <ll> (ww+1,0));
	for(ll i=0;i<n;i++){
		for(ll j=0;j<=ww;j++){
			if(i==0){
				dp[i][j]=(w[i]<=j?v[i]:0);
				continue;
			}
			if(w[i]<=j)
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
			else
				dp[i][j]=dp[i-1][j];
		}
	}
	cout<<dp[n-1][ww]<<"\n";
	
}

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

struct Fast {Fast(){cin.tie(0);ios::sync_with_stdio(0);}} fast;
using intpair = pair<int, int>;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define ceiv(a, b) ((int)((a) + (b) - 1)/(int)(b))
#define int long long

signed main(){
    int n; cin >> n;
    vector<int> A(n), B(n), C(n);
    rep(i,n) cin >> A[i];
    rep(i,n) cin >> B[i];
    rep(i,n) cin >> C[i];
    sort(ALL(A)); sort(ALL(B)); sort(ALL(C));
    
    vector<int> B_cnt(n, 0);
    int c = 0;
    rep(b,n){
        for(; c < n; c++){
            if(B[b] < C[c]) break;
        }
        if(B[b] < C[c]) B_cnt[b] = n - c;
    }
    
    for(int i = n-1; i > 0; i--){
        B_cnt[i-1] += B_cnt[i];
    }
    
    int ans = 0;
    int b = 0;
    rep(a,n){
        for(; b < n; b++){
            if(A[a] < B[b]) break;
        }
        if(A[a] < B[b]) ans += B_cnt[b];
    }
    
    cout << ans << endl;
}

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

int main(){
  int N,sum=0,i;
  cin >> N;
  for(i=10;i<=N;i*=100){
    sum += i*9/10;
  }
  if(N>=i/10)
  	sum +=  (N-(i/10))/(i/10) *(i/10) + N%(i/10) + 1;
  cout << sum <<endl;

}

Measured memory_bytes: 256
import sys
from functools import reduce
import copy
import math
from pprint import pprint
import collections


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def int_inputs(num_of_input):
    ins = [int(input()) for i in range(num_of_input)]
    return ins


def solve(inputs):
    N = len(inputs) // 2
    stores_hour = list(map(string_to_int, inputs[:N]))
    benefit_table = list(map(string_to_int, inputs[N:]))

    pattern_num = 2 ** 10

    max_benefit = None
    for i in range(1, pattern_num):
        bits = bin(i)[2:]
        less_digit = 10 - len(bits)
        zero_padding = ['0' for i in range(less_digit)]
        pattern = zero_padding + list(bits)

        benefit = 0
        for i, store in enumerate(stores_hour):
            match_count = 0
            for j, t in enumerate(store):
                if int(pattern[j]) == 1 and t == 1:
                    match_count += 1
            benefit += benefit_table[i][match_count]
        if max_benefit is None or max_benefit < benefit:
            max_benefit = benefit
    return max_benefit


def string_to_int(string):
    return list(map(int, string.split()))


if __name__ == "__main__":
    N = int(input())
    ret = solve(inputs(N * 2))
    print(ret)


Measured memory_bytes: 3808
#include <bits/stdc++.h>
using namespace std;
int main () {
  int N;
  cin >> N;
  double x;
  string u;
  double sum = 0;
  for (int i = 0; i < N; i++) {
    cin >> x >> u;
    if (u == "JPY") sum += x;
    else sum += x * 380000.0;
  }
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ALL(A) (A).begin(), (A).end()
#define ll long long
#define rep(i, n) for (int i = 0; i < (n); i++)

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

const ll mod = 1e9 + 7;
const ll INF = -1 * ((1LL << 63) + 1);
const int inf = -1 * ((1 << 31) + 1);

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int n;
    cin >> n;
    vector<pair<int,int>> r(n),b(n);
    rep(i,n)cin >> r[i].first >> r[i].second;
    rep(i,n)cin >> b[i].second >> b[i].first;
    vector<bool> used(n,0);
    sort(ALL(r),greater<>());
    sort(ALL(b));
    rep(i,n)swap(b[i].first,b[i].second);
    int ans = 0;
    rep(i,n){
        rep(j,n){
            if(r[i].first < b[j].first && r[i].second < b[j].second && !used[j]){
                ans++;
                used[j] = 1;
                break;
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
using namespace std;
typedef long long int ll;
const int INF = 100000000;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
int main(){
    int a, b;
    vector <int> ans;
    while(cin >> a >> b){
        int c = a + b, count = 0;
        while(c){
            count++;
            c /= 10;
        }
        cout << count << endl;
    }
    return 0;
    
}

Measured memory_bytes: 1160
# coding: utf-8

N, K = map(int, input().split())
p = list(map(int, input().split()))

expect = [(p[i]+1)/2 for i in range(N)]

max_sum = sum(expect[:K])
new_sum = sum(expect[:K])
for i in range(0, N-K):
    new_sum += expect[i+K] - expect[i]
    if max_sum < new_sum:
        max_sum = new_sum

print(max_sum)


Measured memory_bytes: 77448
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int h = sc.nextInt();
		int w = sc.nextInt();
		char[][] a = new char[h][w];
		int c = 0;
		for(int i=0; i<h; i++){
			String s = sc.next();
			for(int j=0; j<w; j++){
				a[i][j] = s.charAt(j);
				if(a[i][j] == '#'){
					c++;
				}
			}
		}
		sc.close();
		
		if(c == h+w-1){
			System.out.println("Possible");
		}else{
			System.out.println("Impossible");
		}

	}

}

Measured memory_bytes: 10188
#define ENABLE_DEBUG 1
// Kana's kitchen {{{
#include<bits/stdc++.h>
#define ALL(v) std::begin(v),std::end(v)
#define LOOP(k) for(i64 ngtkana_is_a_genius=0; ngtkana_is_a_genius<(i64)k; ngtkana_is_a_genius++)

using i32 = std::int_least32_t;
using i64 = std::int_least64_t;
using u32 = std::uint_least32_t;
using u64 = std::uint_least64_t;
using usize = std::size_t;

template <class T, class U> using pair = std::pair<U, T>;
template <class T> using diag_pair = std::pair<T, T>;
template <class... Args> using tuple = std::tuple<Args...>;
template <class T> using vec = std::vector<T>;
template <class T> using numr = std::numeric_limits<T>;

#ifdef NGTKANA
#include<debug.hpp>
#else
#define DEBUG(...)(void)0
#endif
/*}}}*/

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    std::cout << std::setprecision(15) << std::fixed;

    usize n, m;
    std::cin >> n >> m;
    vec<vec<diag_pair<usize>>> g(n);
    for (usize i=0; i<m; i++) {
        usize u, v;
        std::cin >> u >> v;
        u--, v--;
        g.at(u).emplace_back(v, i);
        g.at(v).emplace_back(u, i);
    }

    usize ans = 0;
    for (usize ph=0; ph<m; ph++) {
        vec<usize> que = {0}, ckd(n);
        for (usize i=0; i<que.size(); i++) {
            usize x = que.at(i);
            ckd.at(x) = true;
            for (auto&& e: g.at(x)) {
                usize y, j;
                std::tie(y, j) = e;
                if (ckd.at(y) || j==ph) continue;
                que.push_back(y);
            }
        }
        ans += !std::all_of(ALL(ckd), [](usize x){ return x; });
    }
    std::cout << ans << '\n';
}


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

#define range 100005
#define mod 1000000007
#define eps 1e-9
#define PI 3.14159265358979323846
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define ALL(V) V.begin(), V.end()
#define _ <<" "<<
#define int long long 

using namespace std;

typedef long long ll;
typedef vector <int> vi;
typedef vector<vi> vvi;
typedef pair <int, int> ii;
typedef pair<int, pair<int,int> > iii;
typedef vector<ii> vii;
typedef vector<iii> viii;

int D;

string K;

int dp[20000][200];
int output=0;


signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//freopen("test.txt","r",stdin);
	cin>>K>>D;
	for(int i=0;i<10;i++)
	{
		dp[0][i%D]+=1;
	}
	for(int i=0;i<K.length();i++)
	{
		for(int j=0;j<D;j++)
		{
			if(dp[i][j]>0)
			{
				for(int k=0;k<10;k++)
				{
					int remain = (j + k)%D;
					dp[i+1][remain]+=dp[i][j];
					dp[i+1][remain]%=mod;
				}
			}
		}
	}
	int summu = 0;
	reverse(K.begin(),K.end());
	for(int i=K.length()-1;i>=0;i--)
	{
			for(int k=0;k<(K[i] - '0');k++)
			{
				int remain = ( (- summu - k)%D + D)%D;
				if(i==0)
				{
					if(remain==0)
					{
						output+=1;
						output%=mod;
					}
				}
				else
				{
				  output +=dp[i-1][remain];
				  output%=mod;
				}
			}
		summu+=(K[i]-'0');
		summu%=D;
	}
	if(summu==0)
	{
		output+=1;
		output%=mod;
	}
	output = (output -1 + mod)%mod;
	cout<<output<<endl;
	return 0;
}

Measured memory_bytes: 16640
#include<bits/stdc++.h>
using namespace std;
int main(){
  int b[27]={};
  string s;
  cin>>s;
  for(int i=0;i<s.size();i++){
    b[(int)s[i]-'a']++;//=!b[(int)s[i]-'a'];
  }
  string ans="Yes";
  for(int i=0;i<27;i++){
    if(b[i]%2==1) ans="No";
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
a, b = map(int, input().split())
h = 0
hs = []
for i in range(1, 1000):
    h += i
    hs.append(h)
for i in range(998):
    if (hs[i] - a) == (hs[i + 1] - b):
        print(hs[i] - a)
        exit()


Measured memory_bytes: 38256
#include<iostream> //cinなど
#include<string> //文字列
#include<algorithm> //sort など
#include<math.h> //paw(冪乗など)
#include<set> // 集合
#include<map> //写像
#include<stdio.h> //printf
#include<stack>

using namespace std;


int main(){
   int X,t;
   cin>> X >> t ;
   if(X>=t){
     cout<< X - t<< endl;
   }else{
     cout<< 0 << endl;
   }
   return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MIN(a,b) (((a)<(b))?(a):(b))
using namespace std;

int main(){
    int n, i;
    cin >> n;
    int h[n+1], dp[n+1];
    for(i = 1; i <= n; i++){
        cin >> h[i];
    }
    h[0] = 0;
    dp[0] = 1000000;
    dp[1] = 0;
    for(i = 1; i < n; i++){
        dp[i+1] = MIN(dp[i] + abs(h[i] - h[i+1]), dp[i-1] + abs(h[i-1]- h[i+1]));
    }
    cout << dp[n] << endl;

}

Measured memory_bytes: 1024
def main():
    #from sys import stdin, setrecursionlimit
    #setrecursionlimit(10**9)
    #r = input()
    #n = int(input())
    #a, b = map(int, input().split())
    #s, y = input().split()
    #a = input().split()
    #a = [int(input()) for i in range(n)]
    #a = list(map(int, input().split()))
    #a = [list(map(int, input().split())) for i in range(n)]
    #a = [int(s) - 1 for s in input().split()]
    #l=[int(input()) for _ in range(int(input()))]
    #res = 0
    n = list(map(int,input().split()))
    maisu = max(n[3],n[4])
    ans = [0]*(maisu+1)
    for i in range(maisu+1):
        ans[i] = n[2]*i*2+n[0]*max(0,(n[3]-i))+n[1]*max(0,(n[4]-i))
    print(min(ans))

if __name__ == '__main__':
    main()


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

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

using ll = long long;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int INF = 1<<30;
const ll mod = 1000000007LL;

int main() {
  ll N;
  cin>>N;
  vector<ll> v(N);
  for(ll i = 0; i < N; i++) cin>>v[i];
  sort(v.begin(),v.end());
  if(v[N-1]>0&&v[0]<0){
    ll ans = 0;
    for(auto x:v) ans+=abs(x);
    cout<<ans<<endl;
    ll t = v[N-1];
    ll i = 0;
    while(v[i+1]<=0){
      cout<<t<<" "<<v[i]<<endl;
      t-=v[i];
      i++;
    }
    ll j = N-2;
    ll s = v[i];
    while(v[j]>0){
      cout<<s<<" "<<v[j]<<endl;
      s-=v[j];
      j--;
    }
    cout<<t<<" "<<s<<endl;
  }
  if(v[0]>=0){
    ll ans = 0;
    for(ll i = 0; i < N; i++) {
      if(i==0) ans-=v[i];
      else ans+=v[i];
    }
    cout<<ans<<endl;
    ll t = v[0];
    for(ll i = 1; i < N-1; i++){
      cout<<t<<" "<<v[i]<<endl;
      t-=v[i];
    }
    cout<<v[N-1]<<" "<<t<<endl;
  }
  else if(v[N-1]<=0){
    ll ans = 0LL;
    for(ll i = 0; i < N; i++){
      if(i==N-1) ans-=v[i];
      else ans+=v[i];
    }
    cout<<abs(ans)<<endl;
    ll t = v[N-1];
    for(int i = 0; i < N-1; i++){
      cout<<t<<" "<<v[i]<<endl;
      t-=v[i];
    }
  }
}

Measured memory_bytes: 2688
process.stdin.on('data', function(chunk) {
  var inputs = chunk.toString().trim();
  var r = Number(inputs);
  console.log(Math.PI * Math.pow(r,2)
,2*Math.PI*r
  	);
  // ????????????????????????
});
process.stdin.resume();
process.stdin.setEncoding('utf8');

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

namespace AtCoder.Abc
{
    public class QuestionA
    {
        public static void Main(string[] args)
        {
            var S = Convert.ToChar(Console.ReadLine());
            if (Char.IsUpper(S)) Console.WriteLine("A");
            else Console.WriteLine("a");
        }
    }
}


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

int main() {
    int n, a, b, c, d;
    cin >> n >> a >> b >> c >> d;
    vector<char> s(n);
    for (int i = 0; i < n; i++) {
        cin >> s.at(i);
    }
    bool ans = false;
    if ((a < b && d < c) || (b < a && c < d)) {
        int p1 = max(a, b);
        int p2 = min(c, d);
        for (int i = p1 - 1; i < p2; i++) {
            if (s.at(i - 1) == '.') {
                if (s.at(i) == '.' && s.at(i + 1) == '.') {
                    ans = true;
                }
            }
        }
    }
    else
        ans = true;
    int p3 = min(a, b);
    int p4 = max(c, d);
    for (int i = p3 - 1; i < p4 - 1; i++) {
        if (s.at(i) == '#')
        {
            if (s.at(i + 1) == '#') {
                ans = false;
            }
        }
    }
    if (ans)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll  long long
#define all(v) (v.begin(),v.end())
#define ff first
#define ss second
const ll maxn=1e5+10;
const ll mod=1e9+7;
 
 
/*
N-> 100,W->10^9
we[x] -> 10^9
co[x] -> 10^3
Therefore maxvalue we can get =10^9/10^3=10^6.

*/
 
int main() {
  	fast;
  	ll n,w;
  	cin>>n>>w;
  	ll we[n],co[n];
  	for(ll i=0;i<n;i++){
  		cin>>we[i]>>co[i];
	  }
  		
	vector<ll> dp(maxn+3,INT_MAX);
	//dp[j] = min(dp[j] (j>=co[i]) ? we[i]+dp[j-co[i]] : INT_MAX) //dp[val] represents min weight we can get at value val.
	dp[0]=0;
	for(ll i=0;i<n;++i){
		for(ll j=maxn;j>=co[i];--j){
			dp[j]=min(dp[j],dp[j-co[i]]+we[i]);
		}
	}
	ll ans=0;

	for(ll i= 0; i<=maxn ;++i){
		
		if(dp[i]<=w)
			ans=i;
	}
  	cout<<ans;
  	
}

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

#define int             long long
#define FOR( i, m, n )  for( int (i) = (m); (i) < (n); (i)++ )
#define REP( i, n )     FOR( i, 0, n )
#define REPR( i, m )    for( int (i) = (m); (i) >= 0; (i)-- )
#define REPONE( i, n )  FOR( i, 1, n + 1 )
#define ALL( a )        (a).begin(), (a).end()
#define MP              make_pair

using namespace std;
using P = pair<char, int>;

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

const int INF = 1e18;
const int MOD = 1e9 + 7;

signed main(){
    int time[5];
    int ans = 0, last = 0;
    REP( i, 5 ){
        cin >> time[i];
        ans += time[i];
        time[i] = 10 - time[i] % 10;
        if( time[i] != 10 ){
            ans += time[i];
            chmax( last, time[i] );
        }
        
    }

    ans -= last;
    cout << ans << endl;

}


Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define INF 0x6fffffff
#define INFL 0x6fffffffffffffffLL

int main() {
	ll		a,b,c,h,i,j,k,l,m,n,x,y;
	ll		ans = 0;
	string	t;
	cin >> t;

	n = t.size();
	for(i=0;i<n;i++) {
		if (t[i]=='?') t[i]='D';
	}



	cout << t << endl;
	return 0;
}


Measured memory_bytes: 3756
#include <stdio.h>

#define MOD_BY 1000000007

int add(int a, int b) {
	return a + b - MOD_BY * (a + b >= MOD_BY);
}

char L[114514];

int memo[114514][2];

int asumisu(int idx, int sati) {
	int answer;
	int mizuhasu;
	if (L[idx] == '\0') return 1;
	if (memo[idx][sati]) return ~memo[idx][sati];
	/* 0 0 */
	answer = asumisu(idx + 1, sati && L[idx] == '0');
	/* 0 1 or 1 0 */
	if (!sati || L[idx] == '1') {
		mizuhasu = asumisu(idx + 1, sati);
		answer = add(answer, add(mizuhasu, mizuhasu));
	}
	return ~(memo[idx][sati] = ~answer);
}

int main(void) {
	if (scanf("%114513s", L) != 1) return 1;
	printf("%d\n", asumisu(0, 1));
	return 0;
}


Measured memory_bytes: 7296
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <algorithm>

#define MOD7 1000000007
#define MOD9 1000000009

#define rep(i, n) for (int i = 0; i < (n); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()

using namespace std;

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

int nextInt() {int a; cin >> a; return a;}
char nextChar() {char a; cin >> a; return a;}
double nextDouble() {double a; cin >> a; return a;}
string nextString() {string a; cin >> a; return a;}

void inputVector(vector<int> &v, int &n) {rep(i,n){v.push_back(nextInt());}}
void inputVector(vector<double> &v, int &n) {rep(i,n){v.push_back(nextDouble());}}
void inputVector(vector<string> &v, int &n) {rep(i,n){v.push_back(nextString());}}

int memo[86500];

int timeToInt(string s) {
    int ret = 0;
    ret += (s[0] - '0') * 36000;
    ret += (s[1] - '0') * 3600;
    ret += (s[3] - '0') * 600;
    ret += (s[4] - '0') * 60;
    ret += (s[6] - '0') * 10;
    ret += (s[7] - '0') * 1;
    return ret;
}

signed main() {
    int n;
    while (cin >> n) {
	if (!n) break;

	memset(memo, 0, sizeof(memo));

	rep(i, n) {
	    string s, t;
	    cin >> s >> t;
	    int t1 = timeToInt(s), t2 = timeToInt(t);
	    memo[t1]++;
	    memo[t2]--;
	}
	REP(i, 1, 86400) {
	    memo[i] += memo[i - 1];
	}
	int ret = 0;
	rep(i, 86450) ret = max(ret, memo[i]);
	cout << ret << endl;
    }

    return 0;
}

Measured memory_bytes: 3280
import math
N=int(input())
X=[0.0]*N
Y=[0.0]*N
S=0.0
for i in range(N):
    X[i],Y[i]=map(int,input().split())

for j in range(N-1):
    for k in range(j+1,N):
        S+=math.sqrt((X[j]-X[k])**2+(Y[j]-Y[k])**2)
        
print(round(S*2/N,10))

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

int main(){
  int l,r;
  cin >> l >> r;

  bool check = (r - l + 1 >= 2019);
  l %= 2019;
  r %= 2019;

  if(check || l > r){
    cout << 0 << endl;
  }else{
    int ret = 2019;
    for(int i = l;i < r;i++){
      for(int j = i+1;j <= r;j++){
        ret = min(ret,i*j%2019);
      }
    }
    cout << ret << endl;
  }
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys
import collections


def solve(S: str):
    count_dict = collections.defaultdict(int)
    for s in S:
        count_dict[s] += 1
    print(min(count_dict['0'],count_dict['1'])*2)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = str(next(tokens))  # type: int
    solve(S)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3436
N,X,M=map(int, input().split())

ans=0
count=0
now=X
done=[-1]*(M-1)
L=[]
if now==0:
    print(ans)
    exit()
j=False
while True:
    if count==N:
        break

    if now==0:
        print(ans)
        exit()
    else:
        if done[now-1]==-1:
            done[now-1]=1
            L.append(now)
        else:
            for i in range(len(L)):
                if L[i]==now:
                    j=i
            break
    ans+=now
    count+=1
    now=(now**2)%M

if j:
    L=L[j:]

total=sum(L)
length=len(L)

ans+=((N-count)//length)*total
ans+=sum(L[:(N-count)%length])
print(ans)

Measured memory_bytes: 12116
#include<stdio.h>
int main(){
	int A, B, C, D, p, x, y;
	scanf("%d %d %d %d %d", &A, &B, &C, &D, &p);
	
	x = p * A;
	
	y = B;
	if( p > C){
		y = (( p - C) * D) + y;
	}
	
	if( x < y){
		printf("%d\n", x);
	}else{
		printf("%d\n", y);
	}
	return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<string>
#include<algorithm>
#include<iomanip>
using namespace std;
#define pi 3.141592653589793283462
int main(){
	int m,n,p;
	p=0;
	while (1)
	{
		cin>>n;
		if(n==0)
			break;
		for(int i=0;i<n/4;i++){
			cin>>m;
			p+=m;
		}
		cout<<p<<endl;
		m=0;
		p=0;
		n=0;
	}
	return 0;
}

Measured memory_bytes: 1160
N=int(input())
A=[0]+list(map(int,input().split()))+[0]
x=[0]
for i in range(1,2*(10**5+3)):
    x.append(x[-1]+i)
#print(x[:5])
X=0

S=0
E=0
SUM=0
ans=0
for i in range(10**6):
    if S==N+1:
        ans+=x[(S-E-1)]
        break
    if SUM+A[S+1]==SUM^A[S+1]:
        SUM+=A[S+1]
        S+=1
    else:
        ans+=(S-E)
        SUM-=A[E+1]
        E+=1
    #print(ans,S,E,SUM)
print(ans)

Measured memory_bytes: 88428
#include <bits/stdc++.h>
using namespace std;
constexpr long long MOD = 1000000007;
using ll = long long;

int main() {
    ll n, k;
    cin >> n >> k;
    ll a[n];
    for (ll i = 0; i < n; i++) {
        ll p;
        cin >> p;
        p--;
        a[i] = p;
    }
    ll now = 0;
    vector<ll> route;
    map<ll, ll> visited;
    route.push_back(now);
    visited[now]++;
    ll distone;
    ll loop;
    while (true) {
        ll next = a[now];
        now = next;
        route.push_back(now);
        visited[now]++;
        if (visited[now]==2){
            auto itr = find(route.begin(), route.end(), now);
            auto itr2 = find(itr+1, route.end(), now);
            distone = distance(route.begin(), itr);
            loop = distance(itr, itr2);
            break;
        }
    }
    ll t = (long long)route.size();
    if (k < t)
        cout << route[k] + 1 << endl;
    else
        cout << route[distone + (k - distone) % loop] + 1 << endl;
}


Measured memory_bytes: 18616
N, K = [int(x) for x in input().split()]

rngs = [tuple(int(x) for x in input().split()) for _ in range(K)]
rngs.sort()
p = 998244353

dp = [1] + [0] * (N - 1)
imos = [[] for _ in range(N)]
imos[1].append((-1, 0))
for i in range(N - 1):
    for l, r in rngs:
        if i + l < N:
            imos[i + l].append((1, i))
        if i + r + 1 < N:
            imos[i + r + 1].append((-1, i))


for i in range(1, N):
    dp[i] = dp[i - 1]
    for c, j in imos[i]:
        dp[i] += c * dp[j]
        dp[i] %= p

print(dp[N - 1])

Measured memory_bytes: 172252
import java.util.Arrays;
import java.util.Scanner;
 
 
public class Main {
    static boolean[] isDist;
    static int N;
    static int M;
    static int p;
    public static int INF = 1 << 24;
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        N = stdIn.nextInt();
        M = stdIn.nextInt();
        p = stdIn.nextInt();
        Limit = N*50;
        isDist = new boolean[N];
        for(int i = 0; i < M ;i++) {
            int d = stdIn.nextInt();
            isDist[d] = true;
        }
        boolean[] isDist2 = Arrays.copyOf(isDist,N);
         
        solv(1,p,0,0,false,isDist);
        solv(-1,p,0,0,false,isDist2);
        System.out.println(min);
         
    }
    static int min = 1 << 24; 
    static int Limit;
    public static void solv(int vec, int now, int coun, int cos, boolean alC,boolean[] isDist) {
         
        int nowp = now;
        int cost = cos;
        int count = coun;
        while(true) {
            if(min <= cost)return;
            if(nowp == N) nowp = 0;
            else if(nowp == -1) nowp = N-1;
            if(count == M ) {
                if(min > cost)min = cost;
                return;
            }
            if(isDist[nowp]) {
                 
                isDist[nowp] = false;
                count++;
                if(!alC && cost < Limit) {
                    boolean[] isDist2 = Arrays.copyOf(isDist, N);
                     
                    solv(vec*-1,nowp+vec*-1,count,cost+100,true,isDist2);
                }
            }
            if(count == M ) {
                if(min > cost)min = cost;
                return;
            }
            while(true) {
                if(nowp == N) nowp = 0;
                else if(nowp == -1) nowp = N-1;
                if(!isDist[nowp]) {
                    nowp += vec;
                    cost += 100;
                }
                else {
                    break;
                }
            }
        }
    }
}

Measured memory_bytes: 285040
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <queue>
using ll = long long;
using graph = std::vector<std::vector<ll>>;

using namespace std;

int main() {
    int N;
    cin >> N;
    vector<ll> A(N);
    for(int i = 0; i < N; i++){
        cin >> A[i];
    }
    sort(A.begin(),A.end());
    for(int i = 0; i < N-1; i++){
        if(A[i] == A[i + 1]){
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;

}

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

int main(){
    string s;
    cin>>s;
    int n = s.size();
    int mod = 1e9+7;
    vector<vector<int>> dp(n+1,vector<int>(13,0));
    dp[0][0]=1;
    int pt = 1;
    for(int k=1; k<=n; k++){
        if(s[n-k]=='?'){
            for(int i=0; i<=9; i++){
                for(int j=0; j<13; j++){
                    dp[k][(j+i*pt)%13]+=dp[k-1][j];
                    dp[k][(j+i*pt)%13]%=mod;
                }
            }
        }else{
            int num = s[n-k]-'0';
            for(int j=0; j<13; j++){
                dp[k][(j+num*pt)%13]+=dp[k-1][j];
                dp[k][(j+num*pt)%13]%=mod;
            }
        }
        pt=(pt*10)%13;
    }
    cout<<dp[n][5];
    return 0;
}

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

int main()
{
    int n,k;
    cin>>n>>k;
    int arr[n];
    for(int i=0;i<n;i++)
        cin>>arr[i];
    sort(arr,arr+n);
    int sum = 0;
    for(int i=0;i<k;i++)
        sum += arr[i];
    cout<<sum<<endl;
    return 0;
}

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

int main() {
  int N;
  cin >> N;
  vector<int>mochi(N);
  for(int i=0;i<N;i++){
  cin >> mochi.at(i);
  }
  sort(mochi.begin(),mochi.end());
  int c = 1;
  for(int i=0;i<N-1;i++){
  if(mochi.at(i) < mochi.at(i+1)){
  c++;
  }
  }
  cout << c << endl;
}

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

#define REP(i, s, n) for (int i = s; i < n; ++i)
#define rep(i, n) REP(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG false

int main()
{
    int i;
    stack<int> st;
    while (cin >> i)
    {
        if (i == 0)
        {
            cout << st.top() << endl;
            st.pop();
        }
        else
        {
            st.push(i);
        }
    }
    return 0;
}

Measured memory_bytes: 3024
#include <stdio.h>
#include <stdlib.h>

int compare_int(const void *a,const void *b){
  return *(long*)a-*(long*)b;
}

int main(void){
  int N;
  int cnt = 1;
  scanf("%d",&N);

  int A[N];
  for(int i = 0;i < N;i++){
    scanf("%d",&A[i]);
  }

  qsort(A,N,sizeof(int),compare_int);
  int past = A[0];
  for(int i = 0;i < N;i++){
    if(A[i] != past) cnt++;
    past = A[i];
  }
   
  if(cnt%2 == 0) cnt--;
  printf("%d\n",cnt);

  return 0;
}

Measured memory_bytes: 892
#include<deque>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
#include<sstream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
vector<int> a[365];
int b[14];
stack<int> c;
bool fi(int p){
  int i;
  if(!p){
    cout<<c.top();
    c.pop();
    while(!c.empty()){
      cout<<" "<<c.top();
      c.pop();
    }
    cout<<endl;
    return true;
  }
  for(i=0;i<(int)a[p].size();++i){
    if(!b[a[p][i]])
      continue;
    --b[a[p][i]];
    c.push(a[p][i]);
    if(fi(p-a[p][i]))
      return true;
    c.pop();
    ++b[a[p][i]];
  }
  return false;
}

int main(){
  int i,j;
  //vector<int> a[365];
  for(i=1;i<365;++i){
    for(j=1;j<=13;++j){
      if(i<j||(i-j)%j)
	continue;
      a[i].push_back(j);
    }
  }
  int n;
  while(cin>>n,n){
    //int b[14];
    memset(b,0,sizeof(b));
    int sm=0;
    for(i=0;i<n;++i){
      int p;
      cin>>p;
      ++b[p];
      sm+=p;
    }
    if(!fi(sm))
      cout<<"No"<<endl;
  }
  return 0;
}

Measured memory_bytes: 0