akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) Rep(i, 0, n)
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;

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

    int h, w, d;
    cin >> h >> w >> d;
    int n = h * w;
    vector<int> y(n + 1), x(n + 1);
    rep(i, h) rep(j, w)
    {
        int a;
        cin >> a;
        y[a] = i, x[a] = j;
    }
    vector<int> cost(n + 1, -1);
    Rep(i, 1, n + 1)
    {
        if (cost[i] != -1)
            continue;
        int cnt = 0, num = i;
        while (1)
        {
            cost[num] = cnt;
            int nxt = num + d;
            if (nxt > n)
                break;
            cnt += abs(y[num] - y[nxt]) + abs(x[num] - x[nxt]);
            num = nxt;
        }
    }
    int q;
    cin >> q;
    while (q--)
    {
        int l, r;
        cin >> l >> r;
        cout << cost[r] - cost[l] << endl;
    }
}

Measured memory_bytes: 3200
q = int(input())
lr = []
for i in range(q):
    lr.append([int(j)-1 for j in input().split()])

import math
def test_div(index):
    if index < 2:
        return 0
    elif index == 2:
        return 1
    max = math.ceil(math.sqrt(index))+1
    ls = []
    for i in range(2,max):
        if index % i == 0:
            return 0
    return 1

primes = [2]

import time
st = time.time()
#[0] * 100000
ls = []
for i in range(100000):
    ls.append(test_div(i+1))
ls_like = [0] * 100000
for i in range(100000):
    if ls[i]:
        if ls[(i+2)//2-1]:
            ls_like[i] = 1
        else:
            ls_like[i] = 0
    else:
        ls_like[i] = 0

ls_acc = [0]
for i in range(100000):
    ls_acc.append(ls_acc[-1] + ls_like[i])

#print(time.time()-st)


for i in range(q):
    [l,r] = lr[i]
    print(ls_acc[r+1]-ls_acc[l])


Measured memory_bytes: 100024
#include <bits/stdc++.h>
using namespace std;
int n,a[105],b[105];
int main()
{
	cin>>n;
	for(int i=0;i<n-1;i++)
		cin>>b[i];
	a[0]=b[0];
	for(int i=1;i<n-1;i++)
		a[i]=min(b[i-1],b[i]);
	a[n-1]=b[n-2];
	int ans=0;
	for(int i=0;i<n;i++)
		ans+=a[i];
	cout<<ans;
	return 0;		
}

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

class Vertex;

class Adjacent{
  double weight;
  Vertex* vertex;
public:
  Adjacent(double w,Vertex* v):weight(w),vertex(v){};
  bool operator>(const Adjacent &x)const{ return (weight>x.weight);}
  friend class Graph;
  friend class Vertex;
};

class Vertex{
  int value;
  bool flag;
  bool infinity;
  list<Adjacent> adj_list;
  Vertex():value(0),flag(false),infinity(true){}
  friend class Graph;
};

class Graph{
  vector<Vertex*> graph;
public:
  Graph(int size){
    graph.resize(size);
    for(int i=0;i<size;i++){
      graph[i]=new Vertex();
    }
  }

  ~Graph(){
    for(int i=0;i<(int)graph.size();i++){
      delete graph[i];
    }
  }

  void addEdge(int from,int to,int w){
    graph[from]->adj_list.push_back(Adjacent(w,graph[to]));
  }

  void dijkstra(int start){
    Vertex *v=graph[start];
    int n=0;
    bool check=false;
    priority_queue<Adjacent,vector<Adjacent>,greater<Adjacent> > pq;

    while(true){
      v->flag=true;
      n++;
      if(n==(int)graph.size())
	break;
      for(list<Adjacent>::iterator it=v->adj_list.begin();it!=v->adj_list.end();it++){
	Vertex* w=it->vertex;
	if(!w->flag){
	  if(w->infinity || w->value > v->value + it->weight){
	    w->infinity=false;
	    w->value = v->value + it->weight;
	    pq.push(Adjacent(w->value,w));
	  }
	}
      }

      while(true){
	if(pq.empty()){
	  check=true;
	  break;
	}
	v=pq.top().vertex;
	pq.pop();
	if(!v->flag) break;
      }

      if(check) break;

    }

    for(int i=0;i<(int)graph.size();i++){
      if(graph[i]->flag){
	cout<<graph[i]->value<<endl;
      }else{
	cout<<"INF"<<endl;
      }
    }

  }

};

int main(){
  int v=0;
  int e=0;
  int start = 0;
  cin>>v>>e>>start;
  Graph graph(v);
  for(int i=0;i<e;i++){
    int from,to,w;
    cin>>from>>to>>w;
    graph.addEdge(from,to,w);
  }
  graph.dijkstra(start);
  return 0;
}

Measured memory_bytes: 29856
from bisect import bisect_left, bisect_right

def get_primes(n):
    if not isinstance(n, int):
        raise TypeError('n is int-type.')
    if n < 2:
        raise ValueError('n is more than 2')
    
    from math import sqrt 
    def _sieve_of_eratosthenes(n):
        primes = []
        limit = sqrt(n)
        data = [i + 1 for i in range(1, n)]
        while True:
            p = data[0]
            if limit <= p:
                return primes + data
            primes.append(p)
            data = [e for e in data if e % p != 0]
    return _sieve_of_eratosthenes(n)

primes = get_primes(10**5 + 3)
print(primes[bisect_left(primes, int(input()))])

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

int main(){
    char a,b;
    cin >> a >> b;
    if(a<b){
        cout << "<" << endl;
    }
    else if(a==b){
        cout << "=" << endl;
    }
    else{
        cout << ">" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
fn main() {
    input!{
        n: usize,
        a: [i32; n],
    }
    let mut a = (1..).zip(a.iter()).collect::<Vec<_>>();
    a.sort_by_key(|x| x.1);
    for i in a {
        print!("{} ", i.0);
    }
    println!();
}


Measured memory_bytes: 8956
#include <stdio.h>
#include <math.h>
#include <string.h>
int main (void){
        int A,B;
          scanf("%d",&A);
          scanf("%d",&B);
          if (A+B==15) {
            printf("+");
          }else if (A*B==15) {
            printf("*");
          }else{
            printf("x");
          }
        return 0;

}


Measured memory_bytes: 128
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args)throws IOException{
		InputStreamReader isr = new InputStreamReader(System.in);
		BufferedReader reader = new BufferedReader(isr);
		String str, s[];
		
		int n, q, date[];
		x : while(!(str = reader.readLine()).equals("0 0")){
			s = str.split(" ");
			n = Integer.valueOf(s[0]);
			q = Integer.valueOf(s[1]);
			
			date = new int[125];
			for(int i = 0; i < n; i++){
				s = reader.readLine().split(" ");
				for(int j = 1; j <= Integer.valueOf(s[0]); j++){
					date[Integer.valueOf(s[j])]++;
				}
			}
			for(int i = n; i >= q; i--)
				for(int j = 1; j < date.length; j++){
					if(date[j] == i){
						System.out.println(j);
						continue x;
					}
				}
			System.out.println(0);
		}
		reader.close();
	}
}

Measured memory_bytes: 37464
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
using namespace std;
#define ll long long
const int mod = 1000000007;
const ll INF = 1000000000000000000;

vector<ll> ans;
int K;

int main()
{
	cin >> K;
	if (K <= 9) {
		cout << K << endl;
		return 0;
	}
	int cnt = 0;
	for (int i = 1; i < 10; i++) {
		ans.push_back(i);
		cnt++;
		if (cnt == K) {
			cout << ans[cnt - 1] << endl;
			return 0;
		}
	}
	int j = 0;
	while (true) {
		for (int i = max(0ll, ans[j] % 10 - 1); i <= min(9ll, ans[j] % 10 + 1); i++) {
			ans.push_back(ans[j] * 10 + i);
			cnt++;
			//cout << ans[j] * 10 + i << endl;
			if (cnt == K) {
				cout << ans[j] * 10 + i << endl;
				return 0;
			}
		}
		j++;
	}

}

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

long long t[3761];

int main()
{
	long long a;
	cin>>a;
	
	t[0]=100;
	for(int i=1;i<=3760;i++)
		t[i]=t[i-1]+t[i-1]/100;
	cout<<lower_bound(t+1,t+3761,a)-t<<endl;
	return 0;
}

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

struct tree{
    int parent;
    int right_shibling;
    int left_child;
    tree(){
        parent         = -1;
        right_shibling = -1;
        left_child     = -1;
    }
};


int find_root(const vector<tree>& T){
    for (int i = 0; i < T.size(); i++) {
        if (T[i].parent == -1) {
            return i;
        }
    }
}

void calc_depth(int id, vector<int>& D, vector<tree>& T) {
    int dep_from_known = 0;
    int known_id;
    for (known_id = id; D[known_id] == -1; known_id = T[known_id].parent) {
        dep_from_known++;
    }
    int dep = D[known_id] + dep_from_known;
    for (int j = id; D[j] == -1; j = T[j].parent) {
        D[j] = dep--;
    }
}

int main(){
    int n;
    cin >> n;
    vector<tree> T(n);
    vector<int> D(n, -1);
    for (int i = 0; i < n; i++) {
        int id;
        cin >> id;
        int k;
        cin >> k;
        if (k > 0) {
            cin >> T[id].left_child;
            int child = T[id].left_child;
            T[child].parent = id;
            for (int j = 1; j < k; j++) {
                cin >> T[child].right_shibling;
                child = T[child].right_shibling;
                T[child].parent = id;
            }
        }
    }
    int root = find_root(T);
    D[root] = 0;
    for (int i = 0; i < n; i++) {
        calc_depth(i, D, T);
        cout << "node " << i << ": parent = " << T[i].parent;
        cout << ", depth = " << D[i] << ", ";
        if (D[i] == 0) {
            cout << "root";
        } else if (T[i].left_child != -1) {
            cout << "internal node";
        } else {
            cout << "leaf";
        }
        cout << ", [";
        for (int child = T[i].left_child; child != -1; child = T[child].right_shibling) {
            cout << child;
            if (T[child].right_shibling != -1) cout << ", ";
        }
        cout << "]" << endl;
    }

    return 0;
}

Measured memory_bytes: 4352
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows;

namespace AtCoder
{

    class Program
    {
        static void Main()
        {
            //ここから

            int[] str = ReadLineToIntArray();
            string ans = str[0] % 2 == 1 && str[1] % 2 == 1 ? "Yes" : "No"; 

            //ここまで
            Console.WriteLine(ans);
            Console.ReadKey();
        }

        static public void Factoring(long num,ref long[] vs)
        {
            if (num == 1)
            {
                vs[1]++;
            }
            for(long i = 2; i < (long)Math.Sqrt(num); i++)
            {
                if (num % i == 0)
                {
                    vs[i]++;
                    Factoring(num / i, ref vs);
                }
            }
            vs[1]++;
        }


        long mod = 1000000007;
        static public void Swap<T>(ref T a,ref T b) { T temp = a;a = b;b = temp; }
        static public long GCD(int a, int b){ return b != 0 ? GCD(b, a % b) : a;}
        static public long LCM(int a, int b){ return (long)a * b / GCD(a, b); }
        static public int Factorial(int a) { return a == 1 ? a : a * Factorial(a - 1); }
        static public int Conbin(int n,int m) { return Factorial(n) / (Factorial(n - m) * Factorial(m)); }

        
        static public string ReadLineToString(){return Console.ReadLine();}
        static public int ReadLineToInt(){return int.Parse(Console.ReadLine());}
        static public long ReadLineToLong() { return long.Parse(Console.ReadLine()); }
        static public string[] ReadLineToStringArray(){return Console.ReadLine().Split(' ').ToArray();}
        static public int[] ReadLineToIntArray(){return Console.ReadLine().Split(' ').Select(int.Parse).ToArray();}
        static public long[] ReadLineToLongArray() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
        static public List<string> ReadLineToStringList(){return Console.ReadLine().Split(' ').ToList();}
        static public List<int> ReadLineToIntList(){return Console.ReadLine().Split(' ').Select(int.Parse).ToList();}
        static public List<long> ReadLineToLongList() { return Console.ReadLine().Split(' ').Select(long.Parse).ToList(); }
    }
    
}


Measured memory_bytes: 13268
#include <bits/stdc++.h>
using namespace std;
int n,m,a[10005],days,ans; 
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
    cin>>a[i];
    ans=ans+a[i];
    }
    if(ans>n)
    cout<<"-1";
    else
    {days=n-ans;
    cout<<days;} 
return 0;
}


Measured memory_bytes: 3608
# -*- coding: utf-8 -*-
import math


def main():

    h, w = map(int, input().split())

    result = 0
    if h == 1 or w == 1:
        result = 1
    else:
        result = w * (h // 2)
        if h % 2 == 1:
            result += math.ceil(w / 2)

    print(int(result))


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>

using namespace std;

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

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

const int INF = 1001001001;

int input_bit()
{
    int r = 0;
    rep(i, 16){
        int b;
        cin >> b;
        r <<= 1;
        r += b;
    }
    return r;
}

int func(int n, int c)
{
    vi a(n);
    rep(i, n) a[i] = input_bit();
    
    vi b(c);
    rep(i, c) b[i] = input_bit();
    
    vvi dp(n+1);
    dp[0].assign(1<<16, -INF);
    dp[0][0] = 0;
    
    rep(i, n){
        dp[i+1].assign(1<<16, -INF);
        rep(m, 1<<16){
            if(dp[i][m] == -INF) continue;
            
            rep(j, c){
                int v = m | a[i];
                int cnt = 0;
                rep(k, 16){
                    if(((v>>k)&1) && ((b[j]>>k)&1)){
                        ++cnt;
                        v ^= 1 << k;
                    }
                }
                dp[i+1][v] = max(dp[i+1][v], dp[i][m]+ cnt);
            }
        }
        dp[i].clear();
    }
    
    return *max_element(dp[n].begin(), dp[n].end());
}


int main()
{
    int n, c;
    while(cin >> n >> c, n){
        cout << func(n, c) << endl;
    }
}

Measured memory_bytes: 9180
N=int(input())
hn = list(map(int,input().split()))
inf=float("inf")
dp=[inf]*(N+2)
dp[0], dp[1] = 0, abs(hn[1]-hn[0])
for i in range(2,N):
    dp[i] = min(dp[i-2]+abs(hn[i]-hn[i-2]), dp[i-1]+abs(hn[i]-hn[i-1]))
print(dp[N-1])

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

using namespace std;

#define fi first
#define se second
#define eb emplace_back
#define mt make_tuple
#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;

const ll INF=LLONG_MAX;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
	ll a; 
	string b;
	cin >> a >> b;
	int n = b[0]-'0';
	int n2 = (b[2]-'0')*10 + b[3]-'0';
	ll ans = a*n + a*n2/100;
	cout << ans << endl;
}
	
// READ & UNDERSTAND
// ll, int overflow, array bounds, memset(0)
// special cases (n=1?), n+1 (1-index)
// do smth instead of nothing & stay organized
// WRITE STUFF DOWN


Measured memory_bytes: 3612
#include<iostream>
#include<string>
using namespace std;
int main() {
	string a;
	cin >> a;
	if (a == "++++") {
		cout << 4;
	}
	else if (a == "+++-" || a == "++-+" || a == "+-++" || a == "-+++") {
		cout << 2;
	}
	else if (a == "++--" || a == "+-+-" || a == "+--+" || a == "-++-" || a == "-+-+" || a == "--++") {
		cout << 0;
	}
	else if (a == "---+" || a == "--+-" || a == "-+--" || a == "+---") {
		cout << -2;

	}
	else {
		cout << -4;
	}
}

Measured memory_bytes: 256
class MyStack:
    def __init__(self, MAX):
        self.top = 0
        self.stack = [0] * MAX
        self.MAX = MAX
        
    def is_empty(self):
        return self.top <= 0
    
    def is_full(self):
        return self.top >= self.MAX - 1
    
    def push(self, entry):
        if self.is_full():
            raise ValueError()
        self.top += 1
        self.stack[self.top] = entry
    
    def pop(self):
        if self.is_empty():
            raise ValueError()
        self.top -= 1
        return self.stack[self.top + 1]
    
    
stack = MyStack(110)
ope = input().split()

for o in ope:
    if o == '+':
        rh = stack.pop()
        lh = stack.pop()
        stack.push(lh + rh)
        
    elif o == '-':
        rh = stack.pop()
        lh = stack.pop()
        stack.push(lh - rh)
        
    elif o == '*':
        rh = stack.pop()
        lh = stack.pop()
        
        stack.push(lh * rh)
        
    else:
        stack.push(int(o))

result = stack.pop()
print(result)



Measured memory_bytes: 5608
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define CK(N, A, B) (A <= N && N < B)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define RREP(i, a, b) for (int i = (b - 1); a <= i; i--)
#define F first
#define S second
#define ll long long

const int INF = 1e9;
const long long LLINF = 1e18;

using namespace std;

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

/*==================================================*/
/*variable*/
int N, K;
int x, y;
char c;

int d[2010][2010];

/*==================================================*/
/*function*/
int cal(int y1, int x1, int y2, int x2){

    //cout<<y1<<", "<<x1<<", "<<y2<<", "<<x2<<endl;

    int ret = 0;

    if(x1 >= 2*K || y1 >= 2*K || x2 < 0 || y2 < 0) return ret;  //全くの範囲外

    if(x1 < 0) x1 = 0;  //はみ出しをカット
    if(y1 < 0) y1 = 0;
    if(x2 >= 2*K) x2 = 2*K-1;
    if(y2 >= 2*K) y2 = 2*K-1;

    ret = d[y2][x2];    //累積和で計算
    if(y1-1 >= 0) ret -= d[y1-1][x2];
    if(x1-1 >= 0) ret -= d[y2][x1-1];
    if(y1-1 >= 0 && x1-1 >= 0) ret += d[y1-1][x1-1];

    //cout<<"=> "<<y1<<", "<<x1<<", "<<y2<<", "<<x2<<": "<<ret<<endl;

    return ret;
}

/*==================================================*/

int main() {
    cin>>N>>K;
    REP(i,0,N){
        cin>>x>>y>>c;
        x %= (2*K);
        y %= (2*K);
        if(c == 'W'){
            y = (y + K) % (2*K);
        }
        d[y][x]++;
    }

    //２次元累積和の準備
    REP(i,0,2*K+1){
        REP(j,0,2*K+1){
            d[i][j+1] += d[i][j];
        }
    }
    REP(j,0,2*K){
        REP(i,0,2*K){
            d[i+1][j] += d[i][j];
        }
    }

    int ans = 0;

    //塗り方を全通り試す
//    REP(i,0,2*K){
//        REP(j,0,2*K){
//            //各塗り方で黒い部分に含まれる点を数える（二次元累積和）
//            int t = cal(i,j,i+K-1, j+K-1) +
//                    cal(i-K,j-K,i-1, j-1) +
//                    cal(i-K,j+K,i-1, j+2*K-1) +
//                    cal(i+K,j-K,i+2*K-1, j-1) +
//                    cal(i+K,j+K,i+2*K-1, j+2*K-1);
//            ans = max(ans, t);
//        }
//    }

    REP(i,0,2*K){
        REP(j,0,2*K){
            int t = cal(i-K+1,j-K+1,i,j) +
                    cal(i+K+1,j-K+1,i+2*K,j) +
                    cal(i-K+1,j+K+1,i,j+2*K) +
                    cal(i+1,j+1,i+K,j+K) +
                    cal(i+K+1,j+K+1,i+2*K,j+2*K) +

                    cal(i-3*K+1,j-K+1,i-2*K,j) +
                    cal(i-K+1,j-3*K+1,i,j-2*K) +
                    cal(i-2*K+1,j-2*K+1,i-K,j-K) +
                    cal(i-3*K+1,j-3*K+1,i-2*K,j-2*K) +

                    cal(i+1,j-2*K+1,i+K,j-K);
            ans = max(ans, t);
            //cout<<endl;
        }
    }

    cout<<ans<<endl;

    return 0;
}


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

int main() {
	int X, Y; cin >> X >> Y;
	int re=0;

	if (X == 1) re += 300000;
	else if (X == 2) re += 200000;
	else if (X == 3) re += 100000;

	if (Y == 1) re += 300000;
	else if (Y == 2) re += 200000;
	else if (Y == 3) re += 100000;

	if (X == 1 && Y == 1) re += 400000;

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

	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>

#define N 1000

int max(int x,int y){
  return (x<y)?y:x;
}

int lcs(char *A,char *B){
  int M[N+1][N+1];
  int i,j,Asize,Bsize,maxn=0;
  
  Asize=strlen(&A[1]);  
  Bsize=strlen(&B[1]); 

  
  for(i=0;i<Asize;i++)M[i][0]=0;
  for(i=1;i<Bsize;i++)M[0][i]=0;

  for(i=1;i<=Asize;i++){
    for(j=1;j<=Bsize;j++){
      if(A[i]==B[j])M[i][j]=M[i-1][j-1]+1;
      else M[i][j]=max(M[i-1][j],M[i][j-1]);
     
      maxn=max(maxn,M[i][j]);
    }
  }
  return maxn;
}

int main(){
  int n,i;
  char X[N+1],Y[N+1];
 
  scanf("%d",&n);
 
  for(i=0;i<n;i++){
    scanf("%s%s",&X[1],&Y[1]);
    printf("%d\n",lcs(X,Y));
  }

  return 0;
}




Measured memory_bytes: 5660
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define _for(i,a,b) for(int i = (a);i<(b);i++)
#define endl  '\n'
#define inf 0x3f3f3f3f
#define ull unsigned long long  
using namespace std;
const int mod=1e9+7;
const int MAX=2e5+7;
const double pi=6.28318530717958623200;
//ll a[MAX];
int main()
{
 	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 	double r;
 	cin>>r;
 	cout<<fixed<<setprecision(20)<<r*pi;
 	
}

Measured memory_bytes: 3796
A,B=map(int,input().split())
 
if A>0:
  print('Positive')
elif A==0 or B==0:
  print('Zero')
elif A<0 and 0<B:
  print('Zero')
else:
  if A==B:
    print('Negative')
  elif (B-A)%2==0:
    print('Negative')
  else:
    print('Positive')
    

Measured memory_bytes: 9032
#define  _USE_MATH_DEFINES

#define  rep(i, n) for(int i = 0; i < n; i++)
#define  repx(i, a, n) for(int i = a; i < n; i++)
#define  loop while(1)
#define  lli long long int
#define  aryout(ary) rep(i, ary.size()) cout << ary[i] << (i < ary.size() - 1 ? " " : "\n");
#define  arysort(v) sort(v.begin(), v.end())
#define  aryreverse(v) reverse(v.begin(),v.end())
#define  arysum(v) accumulate(v.begin(), v.end(), 0)
 
#include <iostream>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <utility>
#include <set>

using namespace std;

int main() {

  int n, m;
  cin >> n >> m;

  priority_queue<int> que;
  rep(i, n) {
    int x;
    cin >> x;
    que.push(x);
  }

  rep(i, m) {
    int tmp = que.top();
    que.pop();
    que.push(tmp / 2);
  }

  lli ans = 0;
  while (que.size()) {
    ans += que.top();
    que.pop();
  }

  cout << ans << endl;

  return 0;
}


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

int clock (int a, int b){
    return a + b;
}

int main (){
    int a, b, c;
    cin >> a >> b;
    c = clock(a,b);
    if (clock(a,b)>=24){
        c = c- 24;
    }
    cout << c << endl;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>

int main()
{
	int i, j;
	for(i = 1; i <= 9; i++)
	{
		for(j = 1; j <= 9; j++)
		{
			printf("%dx%d=%d\n",i,j,i*j);
		}
	}
}

Measured memory_bytes: 920
//To debug :  g++ -g file.cpp -o code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,n) for(i=a;i<n;++i)
#define irep(i,n,a) for(i=n;i>a;--i)
#define mod 1000000007
#define pb push_back
#define big 9223372036854775807;
#define big1 LONG_MAX
#define big2 INT_MAX
#define big3 1000000000
#define sma1 LONG_MIN
#define sma2 INT_MIN
#define sma3 -1000000000;
#define mp make_pair
#define dub double
#define ivec vector<int>
#define lvec vector<long long>
#define cvec vector<char>
#define svec vector<string>
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
 

ll a[1001][1001];
char g[1001][1001];


ll fun(int h,int w)
{

	if(h<1 || w<1)
		return 0;
	else if(a[h][w]!=-1)
	{
		//cout<<"hERE\n";
		return a[h][w];
	}
	else if(g[h][w]=='#')
		return 0;
	else if(h==1 && w==1)
		return 1;
	else
	{
		a[h][w]=(fun(h-1,w)+fun(h,w-1))%mod;
		return a[h][w];
	}
}

int main()
{

	int h,w,i,j;
	char c;
	cin>>h>>w;

	for(i=0;i<1001;++i)
	{
		for(j=0;j<1001;++j)
				a[i][j]=-1;
	}


	for(i=1;i<(h+1);++i)
	{
		for(j=1;j<(w+1);++j)
		{
			//cout<<"Here\n";
			//cin>>c;
			cin>>g[i][j];
		}
	}


//	cout<<h<<" "<<w<<"\n";

	cout<<fun(h,w)%mod;



	return 0;
}

Measured memory_bytes: 9088
//by xiqiao
#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
typedef long long ll;
int n,m,Q;
struct node{
	int x,d,c;
}a[maxn];
vector <int> v[maxn];
int col[maxn];
int f[maxn][11];
void dfs(int x,int d,int c){
	if(f[x][d])return;
	if(!col[x])col[x]=c;
	if(d==0)return;
	f[x][d]=1;
	for(int i=0;i<(int)v[x].size();i++){
		dfs(v[x][i],d-1,c);
	}
}

int main(){
	//freopen("1.in","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;scanf("%d%d",&x,&y);
		v[x].push_back(y);v[y].push_back(x);
	}
	scanf("%d",&Q);
	for(int i=1;i<=Q;i++){
		scanf("%d%d%d",&a[i].x,&a[i].d,&a[i].c);
	}
	for(int i=Q;i>=1;i--){
		dfs(a[i].x,a[i].d,a[i].c);
	}
	for(int i=1;i<=n;i++)printf("%d\n",col[i]);
	return 0;
}

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

int main() {
	int n;cin>>n;
	if(n<105) cout<<"0"<<endl;
	else if(n<135) cout<<"1"<<endl;
	else if(n<165) cout<<"2"<<endl;
	else if(n<189) cout<<"3"<<endl;
	else if(n<195) cout<<"4"<<endl;
	else cout<<"5"<<endl;
	return 0;
}

Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author champon
 */

#include <iostream>
#include <fstream>

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1e18
#define ceill(a, b) (a+b-1)/b
#define ok cout << "ok" << endl;
#define sp << " " <<
ll mod = 1e9+7;
void ans(bool b, ostream& out=cout){ out << (b ? "Yes" : "No") << endl; }
void ans2(bool b, ostream& out=cout){ out << (b ? "YES" : "NO") << endl; }
template<typename T> inline bool chmax(T &a, T b){ if(a<b) a=b; return a<b; }
template<typename T> inline bool chmin(T &a, T b){ if(b<a) a=b; return b<a; }
template<typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val){fill((T*)array, (T*)(array+N), val);}
int dx[] = {1, 0, -1, 0, 1, -1, 1, -1};
int dy[] = {0, 1, 0, -1, 1, -1, -1, 1};

#ifndef INCLUDE_DEBUG_HPP
#define INCLUDE_DEBUG_HPP

class debug
{
public:
    template<typename T> void vdeb(T vec);
    template<typename T1, typename T2> void adeb(T1 *arr, T2 n);
    template<typename T> void mdeb(T mp);
};

#endif //INCLUDE_DEBUG_HPP

template<typename T> void debug::vdeb(T vec)
{
    cout << "#vector set debug" << endl;
    for(auto vv : vec) cout << vv << " ";
    cout << endl;
}

template<typename T1, typename T2> void debug::adeb(T1 *arr, T2 n)
{
    cout << "#adebug" << endl;
    for(int i=0; i<=n; i++) cout << arr[i] << " ";
    cout << endl;
}

template<typename T> void debug::mdeb(T mp)
{
    cout << "#map pair debug" << endl;
    for(auto const& m : mp) cout << m.first sp m.second << endl;
}
debug dbg;

class APlacingMarbles {
public:
	void solve(std::istream& in, std::ostream& out)
	{
	    string s;
	    in >> s;
	    int cnt = 0;
	    for(int i=0; i<3; i++){
	        if(s[i] == '1') cnt++;
	    }
	    out << cnt << endl;
	}
};


int main() {
	APlacingMarbles solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 256
//
//  main.cpp
//  Study
//
//  Created by 佐々木勇星 on 2020/03/12.
//  Copyright © 2020 佐々木勇星. All rights reserved.
//

#include <iostream>
#include <vector>
#include <cmath>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <map>

using namespace std;

int ctoi(char c) {
    switch (c) {
        case '0': return 0;
        case '1': return 1;
        case '2': return 2;
        case '3': return 3;
        case '4': return 4;
        case '5': return 5;
        case '6': return 6;
        case '7': return 7;
        case '8': return 8;
        case '9': return 9;
        default: return 0;
    }
}


int main(int argc, const char * argv[]) {


    long long x, now = 100, ans = 0;
    
    cin >> x;
    
    while(1)
    {
        now += now * 0.01;
        ans++;
        //cout << now << endl;
        
        if(now >= x)
        {
            break;
        }
    }
    
    cout << ans << endl;
    
}


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

int main()
{
  int a[3], min_value, min_index, tmp;
  // テキストファイルから入力するには
  // ./a.out < input.txt
  for(int i=0; i<3; i++){
    cin >> a[i];
  }

  //for(int i=0; i<3; i++){
  //  cout << a[i] << " ";
  //}
  //cout << endl;

  for(int i=0; i<2; i++){
    min_value = a[i];
    min_index = i;
    for(int j=i+1; j<3; j++){
      if(a[j]<min_value){
        min_value = a[j];
        min_index = j;
      }
    }
    tmp = a[i];
    a[i] = a[min_index];
    a[min_index] = tmp;
    //cout << a[0] << " " << a[1] << " " << a[2] << endl;


  }

   cout << a[0] << " " << a[1] << " " << a[2] << endl;


  return 0;

}


Measured memory_bytes: 3100
#include<bits/stdc++.h>
#include<vector>
#include<cmath>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
typedef long long ll;
void chmin(int &a,int b){if(a>b) a=b;} //Compare two numbers and return smaller one in reference variety a

int main()
{
    ll N;
    cin>>N;
    if(N%2==0) cout<<N<<endl; else cout<<N*2<<endl;
}

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

int main(){
  int N,L;
  cin >> N >> L;
  int ans =0;
  int eaten=1000;
  int eaten_i;
  for(int i=0;i<N;i++){
    ans += L+i;
    if(eaten>abs(L+i)){
      eaten = abs(L+i);
      eaten_i=i;
    }
  }
  // cout << ans << endl;
  // cout << eaten_i << endl;
  cout << ans - (L + eaten_i) << endl;

  return 0;
}


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

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

int calc(int *array, int *l, int *a, int n){
	int cost = 0;
	for(int i = 0; i < 3; i++){
		int count = 0;
		int sum = 0;
		for(int j = 0; j < n; j++){
			if(array[j] == i){
				count++;
				sum += l[j];
			}
		}
		if(count == 0)return 10000;
		cost += (count - 1) * 10 + abs(sum - a[i]);
	}
	return cost;
}

int try(int *array, int p, int *l, int *a, int n){
	if(p == n){
		return calc(array, l, a, n);
	}
	int min = 10000;
	for(int i = 0; i < 4; i++){
		array[p] = i;
		int tmp = try(array, p + 1, l, a, n);
		if(tmp < min)min = tmp;
	}
	return min;
}

int main(void){
	int n, a[3];
	int l[10];
	int chk[10];

	scanf("%d %d %d %d", &n, a, a + 1, a + 2);
	for(int i = 0; i < n; i++)
		scanf("%d", l + i);
	qsort(l, n, sizeof(int), comp);
	printf("%d\n", try(chk, 0, l, a, n));
	return 0;
}


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

typedef long long ll;
const int maxn=3e3+10;
ll n,mod,c[maxn][maxn],s[maxn][maxn],ans;

inline ll fpow(ll a,ll n,ll mod) {
	ll res=1;
	for(; n; n>>=1,a=a*a%mod)
		if(n&1ll)
			res=res*a%mod;
	return res;
}

int main() {
	cin>>n>>mod;
	for(int i=0; i<maxn; ++i) {
		c[i][0]=1;
		for(int j=1; j<=i; ++j)
			c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
	}
	for(int i=0; i<maxn; ++i) {
		s[i][0]=1;
		for(int j=1; j<=i; ++j)
			s[i][j]=(s[i-1][j-1]+s[i-1][j]*(j+1))%mod;
	}
	for(int i=0; i<=n; ++i) {
		ll k=c[n][i];
		if((n-i)&1)
			k=(mod-k)%mod;
		ll cnt=0;
		for(ll j=0,y=1; j<=n-i; ++j) {
			ll kind=fpow(2,i,mod);
			(cnt+=s[n-i][j]*y)%=mod;
			y=y*kind%mod;
		}
		(ans+=k*cnt%mod*fpow(2,fpow(2,i,mod-1),mod))%=mod;
	}
	cout<<ans<<endl;
	return 0;
}

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

using namespace std;
#define ll long long
#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
const ll mod = 1e9 + 7;
typedef pair<int,int>           PI;
typedef pair<ll,ll>             PL;
typedef vector<PI>               vip; 
typedef vector<int>             vi;
typedef vector<vi>              vvi;
typedef vector<ll>              vl;
typedef vector<vl>              vvl;








int main (){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n;
    cin >> n;
    string str;
    cin >> str;
    vi e(n);
    vi w(n);
    w[0] = 0;
    e[n-1] = 0;
    REP(i, n-1){
        if(str[i] == 'W'){
            w[i+1] = w[i] + 1;
        }else{
            w[i+1] = w[i];
        }
          
    }
    for(int i = n -1; i >= 1; i--){
        if(str[i] == 'E'){
            e[i-1] = e[i] + 1;
        }else{
            e[i-1] = e[i];
        }
    }

    ll min = 1e9;
    REP(i,n){
        int mini = e[i] + w[i];
        if(mini < min) min = mini;
    }
    cout << min << endl;







    return 0;
}










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

#define pb push_back
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define REP(i,n) for(int _n=n, i=0;i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)
#define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;--i)
using ull = uint64_t;
using ll = int64_t;
using PII = pair<int, int>;
using VI = vector<int>;

string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string) s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B> string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; }
template <typename A> string to_string(A v) {
bool first = true; string res = "{";
for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); }
res += "}"; return res; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H); debug_out(T...); }
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

vector<PII> G[1005][1005];
int dist[1005][1005];
bool visited[1005][1005];
bool cycleFound;


int dfs(PII v) {
    if (visited[v.first][v.second]) {
        cycleFound = true;
        return 0;
    }
    if (SZ(G[v.first][v.second]) == 0) {
        return 1;
    }
    visited[v.first][v.second] = true;
    if (dist[v.first][v.second] != -1) return dist[v.first][v.second];
    int d = 0;
    for (auto p : G[v.first][v.second]) {
        d = max(d, dfs(p));
    }
    visited[v.first][v.second] = false;
    return dist[v.first][v.second] = d + 1;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int N;
    cin >> N;
    int totalM = (N * (N - 1)) / 2;
    vector<VI> V(N + 1, VI(N - 1));
    FOR(i, 1, N) REP(j, N - 1) cin >> V[i][j];
    memset(dist, -1, sizeof(dist));
    FOR(i, 1, N) {
        REP(j, N - 2) {
            int p = V[i][j];
            int q = V[i][j + 1];
            G[min(i, p)][max(i, p)].pb({min(i, q), max(i, q)});
        }
    }

    int d = 0;

    FOR(i, 1, N) {
        int p = V[i][0];
        d = max(d, dfs({min(i, p), max(i, p)}));
        if (cycleFound) {
            cout << "-1\n";
            return 0;
        }
    }
    cout << d << "\n";

}


Measured memory_bytes: 48512
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int x = sc.nextInt();
		int t = sc.nextInt();
		
		int total = 0;
		int res = 0;
		
		while(total < n) {
			
			res += t;
			total += x;
		}
		
		System.out.println(res);
		
		sc.close();
	}

}


Measured memory_bytes: 35720
#include <iostream>

using namespace std;

int main()
{
   
    int m, s;
    
    cin >> m >> s;
    
    while(m != 0 || s != 0)
    {
         int x = 0;
         
    for(int i = 1; i <= m; i++ )
    {
        for(int j = i + 1; j <= m; j++)
        {
            for(int k = j + 1; k <= m; k++)
            {
               
                    if(s == i + j + k)
                    {
                        x++;
                    }
             
            }
        }
    }
    
     cout << x << endl;
     
     cin >> m >> s;
    }
    
   return 0;
}


Measured memory_bytes: 3104
#include <iostream>
using namespace std;
#define rep2(x,from,to) for(int x=(from);x<(to);++(x))
#define rep(x,to) rep2(x,0,to)
bool isOk(int i, int r, int c, bool b[104][104]) {
	if(i%2==0) {
		if(b[r][c-1]==0&&b[r][c+1]==0) {
			if(i==0?b[r-1][c]==0:b[r+1][c]==0) return true;
		}
	} else {
		if(b[r-1][c]==0&&b[r+1][c]==0) {
			if(i==1?b[r][c+1]==0:b[r][c-1]==0) return true;
		}
	}
	return false;
}
int main() {
	int n, a;
	cin >> n;
	bool f = 0;
	rep(i,n) {
		if(f) cout << endl;
		f = 1;
		cin >> a;
		bool b[100+4][100+4] = {};
		rep(i,a+4) {
			b[i][0] = 1;
			b[i][a+3] = 1;
			b[0][i] = 1;
			b[a+3][i] = 1;
		}
		int r = a+1, c = 2, cnt = 0;
		while(1) {
			if(!isOk(cnt, r, c, b)) break;
			while(isOk(cnt, r, c, b)) {
				b[r][c] = 1;
				switch(cnt) {
				case 0: r--;
					break;
				case 1: c++;
					break;
				case 2: r++;
					break;
				case 3: c--;
					break;
				}
			}
			cnt = (cnt+1) % 4;
			switch(cnt) {
				case 0: r--, c++;
					break;
				case 1: c++, r++;
					break;
				case 2: r++, c--;
					break;
				case 3: c--, r--;
					break;
			}
		}
		rep2(i,2,a+2) {
			rep2(j,2,a+2) {
				cout << (b[i][j] ? "#": " ");
			}
			cout << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1168
#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define int long long
#define vec(a,n) vector<int> (a)((n))
#define Vec(a,n) vector<string> (a)((n))
#define P pair<int,int>
#define PQ(n) priority_queue<P,vector<P>,greater<P>> (n)
#define pq(n) priority_queue<int> (n)
using namespace std;

signed main(){
    int n,p,ans=1;
    cin >> n >> p;
    if(n==1){
        cout << p << endl;
        return 0;
    }
    int temp = p;
    for(int i=2; p>=i*i;i++){
        int tmp=temp;
        int x = 1,cnt=0;

        while(x == 1){
            if(tmp%i!=0){
                x=0;
            }
            else{
                cnt++;
                tmp /=i;
            }
        }
        int temp1 = 1;
        REP(j,cnt/n){
            temp1 *= i;
        }
        if(temp1 != 1){
            ans *= temp1;
            REP(k,n){
                temp /= temp1;
            }
        }

    }
    cout << ans << endl;
    return 0;
}


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

#define REP(i,s,n) for(int (i)=s; (i)<(int)(n);(i)++)
#define RIT(it,c) for(__typeof(c.begin()) it = c.begin();it!=c.end();it++)
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x).size()
#define MSET(m,v) memset(m,v,sizeof(m))


using namespace std;


typedef long long LL;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<LL> vL;
typedef vector<bool> vb;
typedef pair<int,vi> iv;
typedef pair<LL,LL> pLL; 
typedef long double LD;

bool Judge(int H,int W, map<char,int> &cnt){
	if(H%2 == 0&& W%2 == 0){
		for(auto p:cnt) if(p.second%4) return false;
		return true;
	}
	else if(H%2 == 0 || W%2 == 0){
		if(H%2) swap(H,W);
		int m = 0;
		for(auto p:cnt){
			if(p.second%2) return false;
			if(p.second%4) ++m;
		}
		if(m > H/2) return false;
		return true;
	}
	else{
		int m1 = 0, m2 = 0;
		for(auto p:cnt){
			if(p.second%2) m1++;
			if(m1>1) return false;
			int k = (p.second/2)*2;
			if(k%4) m2++;
		}
		if(m2 > H/2 + W/2) return false;
		return true;
	}
}

int main(){
	int H,W;
	cin>>H>>W;
	map<char,int> cnt;
	for(int i=0;i<H;++i){
		string tmp;
		cin>>tmp;
		for(int j=0;j<W;++j) cnt[tmp[j]]++;
	}
	if(Judge(H, W, cnt)) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}

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

int main() {
	int h, w;
	cin >>h>>w;
	int s = 0;
	for(int i=0;i<h;i++)
		for (int j = 0; j < w; j++) {
			char a;
			cin >> a;
			if (a == '#')s++;
		}
	if (s == h + w - 1)cout << "Possible" << endl;
	else cout << "Impossible" << endl;
	return 0;
}


Measured memory_bytes: 256
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


# 処理内容
def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    money = 1000
    tmp = A[0]
    for i in range(1, N):
        tmp = min(tmp, A[i])
        if tmp < A[i]:
            m = money // tmp
            money -= m * tmp
            money += m * A[i]
            tmp = A[i]
    
    print(money)


if __name__ == '__main__':
    main()

Measured memory_bytes: 72768
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7

#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(long long i=0;i<x;i++)
#define repn(i,x) for(long long i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
vector<pair<string,P> >vec;
// vector<vector<int>> data(3, vector<int>(4));

#define MAX_N 301
#define INF 10000000000001
long long d[MAX_N][MAX_N];
long long e[MAX_N][MAX_N];


int main(){	
	long long N;
	long long L;
	long long M;
	long long Q;
	scanf("%lld",&N);
	scanf("%lld",&M);
	vector<long long> C(M-1+1);
	vector<long long> A(M-1+1);
	vector<long long> B(M-1+1);
	scanf("%lld",&L);
	for(int i = 0 ; i <= MAX_N-1 ; i++){
		for(int j = 0 ; j <= MAX_N-1 ; j++){
			if (i == j) d[i][j] = 0; else d[i][j] = INF;
			if (i == j) e[i][j] = 1; else e[i][j] = INF;
		}
	}
	for(int i = 0 ; i <= M-1 ; i++){
		scanf("%lld",&A[i]);
		scanf("%lld",&B[i]);
		scanf("%lld",&C[i]);
		A[i]--;
		B[i]--;
		d[A[i]][B[i]] = C[i];
		d[B[i]][A[i]] = C[i];
	}
	scanf("%lld",&Q);
	vector<long long> t(Q-1+1);
	vector<long long> s(Q-1+1);
	for(int i = 0 ; i <= Q-1 ; i++){
		scanf("%lld",&s[i]);
		scanf("%lld",&t[i]);
		s[i]--;
		t[i]--;
	}
	
	for (int k = 0; k < N; k++) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
				if (d[i][j] <= L) e[i][j] = 1;
			}
		}
	}
	for (int k = 0; k < N; k++) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				e[i][j] = min(e[i][j], e[i][k]+e[k][j]);
			}
		}
	}
	for(int i = 0 ; i <= Q-1 ; i++){
		if (e[s[i]][t[i]] != INF) cout << e[s[i]][t[i]]-1 << endl; else cout << "-1" << endl;
	}
	return 0;
}



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

int main(){
    int H, N;
    cin >> H >> N;
    int sum = 0;
    for(int i=0;i<N;i++) {
        int A;
        cin >> A;
        sum += A;
    }
    cout << (sum >= H ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-

import sys
from operator import itemgetter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class UnionFind:
    """ Union-Find木 """

    def __init__(self, n):
        self.n = n
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        # 1-indexedのままでOK、その場合は[0]は未使用
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (n+1)
        # あるノードを根とする集合に属するノード数
        self.size = [1] * (n+1)
        # あるノードを根とする集合が木かどうか
        self.tree = [True] * (n+1)

    def find(self, x):
        """ 根の検索(グループ番号と言えなくもない) """
        # 根ならその番号を返す
        if self.par[x] == x:
            return x
        else:
            # 走査していく過程で親を書き換える
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """ 併合 """
        # 根を探す
        x = self.find(x)
        y = self.find(y)

        # 木かどうかの判定用
        if x == y:
            self.tree[x] = False
            return
        if not self.tree[x] or not self.tree[y]:
            self.tree[x] = self.tree[y] = False

        # 木の高さを比較し、低いほうから高いほうに辺を張る
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        """ 同じ集合に属するか判定 """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """ あるノードの属する集合のノード数 """
        return self.size[self.find(x)]
    
    def is_tree(self, x):
        """ 木かどうかの判定 """
        return self.tree[self.find(x)]

    def len(self):
        """ 集合の数 """
        res = set()
        for i in range(self.n+1):
            res.add(self.find(i))
        # グループ0の分を引いて返却
        return len(res) - 1

N = INT()
XY = []
for i in range(N):
    x, y = MAP()
    XY.append((i, x, y))

edges = []
XY.sort(key=itemgetter(1))
for i in range(N-1):
    i1, x1, _ = XY[i]
    i2, x2, _ = XY[i+1]
    cost = x2 - x1
    edges.append((i1, i2, cost))
XY.sort(key=itemgetter(2))
for i in range(N-1):
    i1, _, y1 = XY[i]
    i2, _, y2 = XY[i+1]
    cost = y2 - y1
    edges.append((i1, i2, cost))

uf = UnionFind(N)
ans = 0
edges.sort(key=itemgetter(2))
for a, b, cost in edges:
    if not uf.same(a, b):
        uf.union(a, b)
        ans += cost
print(ans)


Measured memory_bytes: 52788
while True:

    m,f,r = map(int,input().split())

    total = m+f

    if m == -1 and f == -1 and r == -1:
        break

    if m == -1 or f == -1:
        print("F")
    elif total >= 80:
        print("A")
    elif total >=65 and total < 80:
        print("B")
    elif total >= 50 and total < 65:
        print("C")
    elif r >=50:
        print("C")
    elif total >= 30 and total < 50:
        print("D")
    elif total < 30:
        print("F")

Measured memory_bytes: 7712
r, c = map(int, input().split())
table = []
for i in range(r):
    table.append(list(map(int, input().split())))
    table[i].append(sum(table[i]))

table.append([0 for _ in range(c+1)])

for i in range(r):
    for j in range(c+1):
        table[-1][j] += table[i][j]

for i in range(r+1):
    print(' '.join(map(str,table[i])))



Measured memory_bytes: 5704
#include<iostream>
#include <string>
using namespace std;
int main()
{
	string s,t,u;
	int a,b;
	cin >> s >> t;
	cin >> a >> b;
	cin >> u;
	if (u==s)
		a--;
	else 
		b--;
	cout << a << " " << b;
}

Measured memory_bytes: 256