rt

三彩斑斓的评测记录

对评测记录不感兴趣的dl源码如下

// 

#include<iostream>
#include<iomanip>
#include<vector>
#include<queue>
#include<stack>
#include<stdio.h>
#include<cstring>
#include<string.h>
#include<cstdio>
#include<string>
#include<algorithm>
#include<utility>
#include<limits.h>
#include<map>
#include<set>
using namespace std;

struct node{
	int x, y;
};
int f[2][1010];
bool wall[1010][10010];
int sum_wall[10010];

int n, m, ki;
struct Move{
	int up, down;
}mine_move[10010];

void read()
{
	cin >> n >> m >> ki;
	for(int i = 0; i < n; i++)
	{
		scanf("%d %d", &mine_move[i].up, &mine_move[i].down);
	}
	n++, m++;
	for(int i = 0; i < ki; i++)
	{
		int x, be, en;
		scanf("%d %d %d", &x, &be, &en);
		for(int j = 0; j < m; j++)
		{
			if(j > be && j < en)
			{
				continue;
			}
			wall[j][x] = true;
		}
        for(int j = x; j < n; j++)
        {
            sum_wall[j]++;
        }
	}
	memset(wall[0], 1, sizeof(wall[0]));
}

int max_pass = 0;

int main(){
	read();
	f[0][0] = f[1][0] = -1;
	for(int i = 1; i < n; i++)
	{
//		cout << "x: " << i << endl;
		int up = mine_move[i - 1].up, down = mine_move[i - 1].down;
		for(int j = 1; j < m; j++)
		{
//			cout << "y: " << j << " ";
			if(wall[j][i])
			{
//				cout << "wall" << "   ";
				f[i & 1][j] = -1;
				continue;
			}
			f[i & 1][j] = -1;
			if(j + down < m && f[(i + 1) & 1][j + down] != -1)
			{
				f[i & 1][j] = f[(i + 1) & 1][j + down];
			}
			for(int k = 1; j - k * up > 0; k++)
			{
				if(f[(i + 1) & 1][j - k * up] != -1 && (f[(i + 1) & 1][j - k * up] + k < f[i & 1][j] || f[i & 1][j] == -1))
				{
					f[i & 1][j] = f[(i + 1) & 1][j - k * up] + k;
				}
			}
			if(j == m - 1)
			{
				for(int h = m - 1; h > m - 1 - up; h--)
				{
					if(f[(i + 1) & 1][h] != -1 && (f[(i + 1) & 1][h] + 1 < f[i & 1][j] || f[i & 1][j] == -1))
					{
						f[i & 1][j] = f[(i + 1) & 1][h] + 1;
					}
				}
			}
            if(f[i & 1][j] != -1)
            {
                max_pass = i;
            }
//			cout << f[i & 1][j] << "   ";
		}
//		cout << endl;
	}
	int minn = f[(n - 1) & 1][1];
	for(int i = 2; i < m; i++)
	{
		if((f[(n - 1) & 1][i] < minn || minn == -1)&& f[(n - 1) & 1][i] != -1)
		{
			minn = f[(n - 1) & 1][i];
		}
	}
    if(minn != -1)
    {
	    cout << 1 << endl;
	    cout << minn << endl;
    }
    else
    {
        cout << 0 << endl << sum_wall[max_pass] << endl;
    }
	return 0;
}